Araştırma Makalesi
BibTex RIS Kaynak Göster

Computing the zero forcing number for generalized Petersen graphs

Yıl 2020, , 183 - 193, 07.05.2020
https://doi.org/10.13069/jacodesmath.729465

Öz

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

Teşekkür

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

Kaynakça

  • [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.
Yıl 2020, , 183 - 193, 07.05.2020
https://doi.org/10.13069/jacodesmath.729465

Öz

Kaynakça

  • [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.
Toplam 17 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Mühendislik
Bölüm Makaleler
Yazarlar

Saeedeh Rashidi Bu kişi benim 0000-0002-8262-0910

Nosratollah Shajareh Poursalavatı Bu kişi benim 0000-0003-0046-0325

Maryam Tavakkolı Bu kişi benim 0000-0002-2863-4799

Yayımlanma Tarihi 7 Mayıs 2020
Yayımlandığı Sayı Yıl 2020

Kaynak Göster

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ıs 2020;7(2):183-193. doi:10.13069/jacodesmath.729465
Chicago Rashidi, Saeedeh, Nosratollah Shajareh Poursalavatı, ve Maryam Tavakkolı. “Computing the Zero Forcing Number for Generalized Petersen Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 7, sy. 2 (Mayıs 2020): 183-93. https://doi.org/10.13069/jacodesmath.729465.
EndNote Rashidi S, Shajareh Poursalavatı N, Tavakkolı M (01 Mayıs 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ı, ve M. Tavakkolı, “Computing the zero forcing number for generalized Petersen graphs”, Journal of Algebra Combinatorics Discrete Structures and Applications, c. 7, sy. 2, ss. 183–193, 2020, doi: 10.13069/jacodesmath.729465.
ISNAD Rashidi, Saeedeh vd. “Computing the Zero Forcing Number for Generalized Petersen Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 7/2 (Mayıs 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 vd. “Computing the Zero Forcing Number for Generalized Petersen Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications, c. 7, sy. 2, 2020, ss. 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