| | | |

## Computing the zero forcing number for generalized Petersen graphs

#### Saeedeh RASHİDİ [1] , Nosratollah SHAJAREH POURSALAVATI [2] , Maryam TAVAKKOLI [3]

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 \rightarrow 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$.
Zero forcing number, Generalized Petersen graph, Colin de Verdi\{e}re parameter
• [1] B. Alspach, The classification of hamiltonian of generalized Petersen graphs, J. Combin. Theory Ser. B 34(3) (1983) 293–312.
• [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.
• [3] K. Bannai, Hamiltonian cycles in generalized Petersen graphs, J. Combin. Theory Ser. B 24(2) (1978) 181–188.
• [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.
• [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.
• [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.
• [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.
• [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.
• [9] J. Ebrahimi, B. N. Jahanbakhsh, E. S. Mahmoodian, Vertex domination of generalized Petersen graph, Discrete Math. 309(13) (2009) 4355–4361.
• [10] R. Gera, P. Stanica, The spectrum of generalized Petersen graphs, Australian Journal of Combinatorics, 49 (2011) 39–45.
• [11] L. Hogben, Minimum rank problems, Linear Algebra Appl. 432(8) (2010) 1961–1974.
• [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.
• [13] D. McQuillan, R. B. Richter, On the crossing numbers of certain generalized Petersen graphs, Discrete Math. 104(3) (1992) 311–320.
• [14] G. Salazar, On the crossing numbers of loop networks and generalized Petersen graphs, Discrete Math. 302(1–3) (2005) 243–253.
• [15] A. J. Schwenk, Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, J. Combin. Theory Ser. B 47(1) (1989) 53–59.
• [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.
• [17] M. Zaker, On dynamic monopolies of graphs with general thresholds, Discrete Math. 312(6) (2012) 1136–1143.
Primary Language en Engineering Articles Orcid: 0000-0002-8262-0910Author: Saeedeh RASHİDİ Institution: Shahid Bahonar University of KermanCountry: Iran Orcid: 0000-0003-0046-0325Author: Nosratollah SHAJAREH POURSALAVATI Institution: Shahid Bahonar University of KermanCountry: Iran Orcid: 0000-0002-2863-4799Author: Maryam TAVAKKOLI Institution: Shahid Bahonar University of KermanCountry: Iran This work was supported by Mahani Mathematical Research Center, Shahid Bahonar University of Kerman, Kerman, Iran. Publication Date : May 7, 2020
 Bibtex @research article { jacodesmath729465, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2020}, volume = {7}, pages = {183 - 193}, doi = {10.13069/jacodesmath.729465}, title = {Computing the zero forcing number for generalized Petersen graphs}, key = {cite}, author = {Rashi̇di̇, Saeedeh and Shajareh Poursalavatı, Nosratollah and Tavakkolı, Maryam} }` APA Rashi̇di̇, S , Shajareh Poursalavatı, N , Tavakkolı, M . (2020). Computing the zero forcing number for generalized Petersen graphs . Journal of Algebra Combinatorics Discrete Structures and Applications , 7 (2) , 183-193 . DOI: 10.13069/jacodesmath.729465 MLA Rashi̇di̇, S , Shajareh Poursalavatı, N , Tavakkolı, M . "Computing the zero forcing number for generalized Petersen graphs" . Journal of Algebra Combinatorics Discrete Structures and Applications 7 (2020 ): 183-193 Chicago Rashi̇di̇, S , Shajareh Poursalavatı, N , Tavakkolı, M . "Computing the zero forcing number for generalized Petersen graphs". Journal of Algebra Combinatorics Discrete Structures and Applications 7 (2020 ): 183-193 RIS TY - JOUR T1 - Computing the zero forcing number for generalized Petersen graphs AU - Saeedeh Rashi̇di̇ , Nosratollah Shajareh Poursalavatı , Maryam Tavakkolı Y1 - 2020 PY - 2020 N1 - doi: 10.13069/jacodesmath.729465 DO - 10.13069/jacodesmath.729465 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 183 EP - 193 VL - 7 IS - 2 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.729465 UR - https://doi.org/10.13069/jacodesmath.729465 Y2 - 2019 ER - EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications Computing the zero forcing number for generalized Petersen graphs %A Saeedeh Rashi̇di̇ , Nosratollah Shajareh Poursalavatı , Maryam Tavakkolı %T Computing the zero forcing number for generalized Petersen graphs %D 2020 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 7 %N 2 %R doi: 10.13069/jacodesmath.729465 %U 10.13069/jacodesmath.729465 ISNAD Rashi̇di̇, Saeedeh , Shajareh Poursalavatı, Nosratollah , Tavakkolı, Maryam . "Computing the zero forcing number for generalized Petersen graphs". Journal of Algebra Combinatorics Discrete Structures and Applications 7 / 2 (May 2020): 183-193 . https://doi.org/10.13069/jacodesmath.729465 AMA Rashi̇di̇ S , Shajareh Poursalavatı N , Tavakkolı M . Computing the zero forcing number for generalized Petersen graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2020; 7(2): 183-193. Vancouver Rashi̇di̇ S , Shajareh Poursalavatı N , Tavakkolı M . Computing the zero forcing number for generalized Petersen graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2020; 7(2): 183-193.

Authors of the Article
[1]
[2]
[3]