Computing the zero forcing number for generalized Petersen graphs

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

References

1. [1] B. Alspach, The classification of hamiltonian of generalized Petersen graphs, J. Combin. Theory Ser. B 34(3) (1983) 293–312.
2. [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. [3] K. Bannai, Hamiltonian cycles in generalized Petersen graphs, J. Combin. Theory Ser. B 24(2) (1978) 181–188.
4. [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. [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. [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. [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. [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. [9] J. Ebrahimi, B. N. Jahanbakhsh, E. S. Mahmoodian, Vertex domination of generalized Petersen graph, Discrete Math. 309(13) (2009) 4355–4361.
10. [10] R. Gera, P. Stanica, The spectrum of generalized Petersen graphs, Australian Journal of Combinatorics, 49 (2011) 39–45.
11. [11] L. Hogben, Minimum rank problems, Linear Algebra Appl. 432(8) (2010) 1961–1974.
12. [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. [13] D. McQuillan, R. B. Richter, On the crossing numbers of certain generalized Petersen graphs, Discrete Math. 104(3) (1992) 311–320.
14. [14] G. Salazar, On the crossing numbers of loop networks and generalized Petersen graphs, Discrete Math. 302(1–3) (2005) 243–253.
15. [15] A. J. Schwenk, Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, J. Combin. Theory Ser. B 47(1) (1989) 53–59.
16. [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. [17] M. Zaker, On dynamic monopolies of graphs with general thresholds, Discrete Math. 312(6) (2012) 1136–1143.