Computing the zero forcing number for generalized Petersen graphs
DOI:
https://doi.org/10.13069/jacodesmath.729465Keywords:
Zero forcing number, Generalized Petersen graph, Colin de Verdiere parameterAbstract
Let $G$ be a simple undirected graph with each vertex colored either white or black, $u$ be a black vertex of $G$, and exactly one neighbor $v$ of $u$ be white. Then change the color of $v$ to black. When this rule is applied, we say $u$ forces $v$, and write $u \to v$. A zero forcing set of a graph $G$ is a subset $Z$ of vertices such that if initially the vertices in $Z$ are colored black and remaining vertices are colored white, the entire graph $G$ may be colored black by repeatedly applying the color-change rule. The zero forcing number of $G$, denoted $Z(G)$, is the minimum size of a zero forcing set. In this paper, we investigate the zero forcing number for the generalized Petersen graphs (It is denoted by $P(n,k)$). We obtain upper and lower bounds for the zero forcing number for $P(n,k)$. We show that $Z(P(n,2))=6$ for $n\geq 10$, $Z(P(n,3))=8$ for $n\geq 12$ and $Z(P(2k+1,k))=6$ for $k\geq 5$.
Received: 9 July 2018 | Accepted: 10 October 2019Downloads
References
AIM Minimum Rank – Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428(7) (2008) 1628–1648.
D. Amos, Y. Caro, R. Davila, and R. Pepper, Upper bounds on the zero forcing number of a graph, Theoret. Comput. Sci. 581 (2015) 32–41.
K. F. Benson, D. Ferrero, M. Flagg, V. Furst, L. Hogben, V. Vasilevska, and B. Wissman, Zero forcing and maximum nullity for graph products, Linear Algebra Appl. 532 (2017) 201–229.
F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, and B. Shader, Zero forcing parameters, minimum rank problems, and graph infection, Linear Algebra Appl. 436(11) (2012) 4001–4027.
F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, H. van der Holst, and B. Shader, Zero forcing parameters and minimum rank problems, Linear Algebra Appl. 433(2) (2010) 401–411.
F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche, and H. van der Holst, Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory 72(2) (2013) 146–177.
F. Barioli, S. Fallat, D. Hershkowitz, H. T. Hall, L. Hogben, H. van der Holst, and B. Shader, On the minimum rank of not necessarily symmetric matrices: A preliminary study, Electron. J. Linear Algebra 18 (2009) 126–145.
Y. Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Theory Ser. B 50(1) (1990) 11–21.
J. Ebrahimi, N. Jahanbakht, and E. S. Mahmoodian, Vertex domination of generalized Petersen graphs, Discrete Math. 309(13) (2009) 4355–4361.
R. Gera and P. Stănică, The spectrum of generalized Petersen graphs, Australas. J. Combin. 49 (2011) 39–45.
L. Hogben, Minimum rank problems, Linear Algebra Appl. 432(8) (2010) 1961–1974.
L.-H. Huang, G. J. Chang, and H.-G. Yeh, On minimum rank and zero forcing sets of a graph, Linear Algebra Appl. 432(11) (2010) 2961–2973.
D. McQuillan and R. B. Richter, On the crossing numbers of certain generalized Petersen graphs, Discrete Math. 104(3) (1992) 311–320.
G. Salazar, On the crossing numbers of loop networks and generalized Petersen graphs, Discrete Math. 302(1-3) (2005) 243–253.
A. J. Schwenk, Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, J. Combin. Theory Ser. B 47(1) (1989) 53–59.
H. van der Holst, L. Lovász, and A. Schrijver, The Colin de Verdière graph parameter, in: Graph Theory and Combinatorial Biology, Bolyai Soc. Math. Stud., vol. 7, János Bolyai Math. Soc., Budapest (1999) 29–85.
M. Zaker, On dynamic monopolies of graphs with general thresholds, Discrete Math. 312(6) (2012) 1136–1143.
