TY  - JOUR
T1  - Computing the zero forcing number for generalized Petersen graphs
AU  - Rashidi, Saeedeh
AU  - Shajareh Poursalavatı, Nosratollah
AU  - Tavakkolı, Maryam
PY  - 2020
DA  - May
DO  - 10.13069/jacodesmath.729465
JF  - Journal of Algebra Combinatorics Discrete Structures and Applications
PB  - iPeak Academy
WT  - DergiPark
SN  - 2148-838X
SP  - 183
EP  - 193
VL  - 7
IS  - 2
LA  - en
AB  - Let $G$ be a simple undirected graph with each vertex coloredeither white or black, $ u $ be a black vertex of $ G, $ andexactly one neighbor $ v $ of $ u $ be white. Then change thecolor of $ v $ to black. When this rule is applied, we say $ u $forces $ v, $ and write $ u \rightarrow v $.A $zero\ forcing\ set$ of a graph $ G$ is asubset $Z$ of vertices such that if initially the vertices in $ Z $ are coloredblack and remaining verticesare colored white, the entire graph $ G $ may be colored blackby repeatedly applying thecolor-change rule.The zero forcing number of $ G$, denoted $Z(G), $ is the minimum size of azero 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$.
KW  - Zero forcing number
KW  - Generalized Petersen graph
KW  - Colin de Verdi\`{e}re parameter
CR  - [1] B. Alspach, The classification of hamiltonian of generalized Petersen graphs, J. Combin. Theory Ser.
B 34(3) (1983) 293–312.
CR  - [2] J. S. Alameda, E. Curl, A. Grez, L. Hogben, O. Kingston, A. Schulte, D. Young, M. Young, Families
of graphs with maximum nullity equal to zero–forcing number, Spec. Matrices 6 (2018) 56–67.
CR  - [3] K. Bannai, Hamiltonian cycles in generalized Petersen graphs, J. Combin. Theory Ser. B 24(2) (1978)
181–188.
CR  - [4] AIM Minimum Rank – Special Graphs Work Group: F. Barioli, W. Barrett, S. Butler, S. M. Cioaba,
D. Cvetkovic, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O.
Pryporova, I. Sciriha, W. So, D. Stevanovic, H. van der Holst, K. Vander Meulen, A. Wangsness,
Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428(7) (2008) 1628–1648.
CR  - [5] F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, H. van der Holst, B. Shader, Zero forcing
parameters and minimum rank problems, Linear Algebra Appl. 433(2) (2010) 401–411.
CR  - [6] F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche, 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.
CR  - [7] F. Barioli, S. Fallat, D. Hershkowitz, H. T. Hall, L. Hogben, H. van der Holst, B. Shader, On
the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear
Algebra 18 (2009) 126–145.
CR  - [8] Y. Colin de Verdière, Sur un nouvel invariant des graphs et un critère de planarité, J. Combin.
Theory Ser. B 50 (1990) 11–21.
CR  - [9] J. Ebrahimi, B. N. Jahanbakhsh, E. S. Mahmoodian, Vertex domination of generalized Petersen
graph, Discrete Math. 309(13) (2009) 4355–4361.
CR  - [10] R. Gera, P. Stanica, The spectrum of generalized Petersen graphs, Australian Journal of Combinatorics,
49 (2011) 39–45.
CR  - [11] L. Hogben, Minimum rank problems, Linear Algebra Appl. 432(8) (2010) 1961–1974.
CR  - [12] L. H. Huang, G. J. Chang, H. G. Yeh, On minimum rank and zero forcing sets of a graph, Linear
Algebra Appl. 432(11)( (2010) 2961–2973.
CR  - [13] D. McQuillan, R. B. Richter, On the crossing numbers of certain generalized Petersen graphs, Discrete
Math. 104(3) (1992) 311–320.
CR  - [14] G. Salazar, On the crossing numbers of loop networks and generalized Petersen graphs, Discrete
Math. 302(1–3) (2005) 243–253.
CR  - [15] A. J. Schwenk, Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, J. Combin.
Theory Ser. B 47(1) (1989) 53–59.
CR  - [16] H. van der Holst, L. Lovász, A. Schrijver, The Colin de Verdière graph parameter, Graph Theory
and Combinatorial Biology (Balatonlelle, 1996) volume 7 of Bolyai Soc. Math. Stud., pages 29–85.
János Bolyai Math. Soc., Budapest, 1999.
CR  - [17] M. Zaker, On dynamic monopolies of graphs with general thresholds, Discrete Math. 312(6) (2012)
1136–1143.
UR  - https://doi.org/10.13069/jacodesmath.729465
L1  - https://dergipark.org.tr/en/download/article-file/1078628
ER  -