Research Article
BibTex RIS Cite

Computing the zero forcing number for generalized Petersen graphs

Year 2020, , 183 - 193, 07.05.2020
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$.

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.
Year 2020, , 183 - 193, 07.05.2020
https://doi.org/10.13069/jacodesmath.729465

Abstract

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.
There are 17 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Saeedeh Rashidi This is me 0000-0002-8262-0910

Nosratollah Shajareh Poursalavatı This is me 0000-0003-0046-0325

Maryam Tavakkolı This is me 0000-0002-2863-4799

Publication Date May 7, 2020
Published in Issue Year 2020

Cite

APA Rashidi, 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. https://doi.org/10.13069/jacodesmath.729465
AMA Rashidi S, Shajareh Poursalavatı N, Tavakkolı M. Computing the zero forcing number for generalized Petersen graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. May 2020;7(2):183-193. doi:10.13069/jacodesmath.729465
Chicago Rashidi, Saeedeh, Nosratollah Shajareh Poursalavatı, and Maryam Tavakkolı. “Computing the Zero Forcing Number for Generalized Petersen Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 7, no. 2 (May 2020): 183-93. https://doi.org/10.13069/jacodesmath.729465.
EndNote Rashidi S, Shajareh Poursalavatı N, Tavakkolı M (May 1, 2020) Computing the zero forcing number for generalized Petersen graphs. Journal of Algebra Combinatorics Discrete Structures and Applications 7 2 183–193.
IEEE S. Rashidi, N. Shajareh Poursalavatı, and M. Tavakkolı, “Computing the zero forcing number for generalized Petersen graphs”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 7, no. 2, pp. 183–193, 2020, doi: 10.13069/jacodesmath.729465.
ISNAD Rashidi, Saeedeh et al. “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.
JAMA Rashidi 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:183–193.
MLA Rashidi, Saeedeh et al. “Computing the Zero Forcing Number for Generalized Petersen Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 7, no. 2, 2020, pp. 183-9, doi:10.13069/jacodesmath.729465.
Vancouver Rashidi 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-9.

Cited By

On the Semitotal Forcing Number of a Graph
Bulletin of the Malaysian Mathematical Sciences Society
https://doi.org/10.1007/s40840-021-01236-2