Computing the zero forcing number for generalized Petersen graphs

Year 2020, Volume: 7 Issue: 2, 183 - 193, 07.05.2020

Saeedeh Rashidi Nosratollah Shajareh Poursalavatı Maryam Tavakkolı

https://doi.org/10.13069/jacodesmath.729465

Abstract

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$.

Keywords

Zero forcing number, Generalized Petersen graph, Colin de Verdi\`{e}re parameter

Thanks

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

References

• [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.