Year 2020, Volume 7 , Issue 2, Pages 183 - 193 2020-05-07

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
Subjects Engineering
Journal Section Articles
Authors

Orcid: 0000-0002-8262-0910
Author: Saeedeh RASHİDİ
Institution: Shahid Bahonar University of Kerman
Country: Iran


Orcid: 0000-0003-0046-0325
Author: Nosratollah SHAJAREH POURSALAVATI
Institution: Shahid Bahonar University of Kerman
Country: Iran


Orcid: 0000-0002-2863-4799
Author: Maryam TAVAKKOLI
Institution: Shahid Bahonar University of Kerman
Country: Iran


Thanks This work was supported by Mahani Mathematical Research Center, Shahid Bahonar University of Kerman, Kerman, Iran.
Dates

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 <https://dergipark.org.tr/en/pub/jacodesmath/issue/54201/729465>
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
Saeedeh RASHİDİ [1]
Nosratollah SHAJAREH POURSALAVATI [2]
Maryam TAVAKKOLI [3]