Some Cayley graphs with propagation time 1

Document Type : Research Article


Department of Pure Mathematics, Faculty of Science, Imam Khomeini International University


In this paper we study the zero forcing number as well as the propagation time of Cayley graph $Cay(G,\Omega),$ where $G$ is a finite group and $\Omega \subset G \setminus \lbrace 1 \rbrace$ is an inverse closed generator set of $G$. It is proved that the propagation time of $Cay(G,\Omega)$ is 1 for some Cayley graphs on dihedral groups and finite cyclic groups with special generator set $\Omega$.‎


Main Subjects

[1] A.Abdollahi, E. Vatandoost, Which Cayley graphs are integral? Electron. J. Combin. 16 (2009), no. 1, 1--17.
[2] AIM Minimum Rank-Special GraphsWork Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), no. 7, 1628--1648.
[3] J.S.Alameda, E.Curl, A. Grez, L. Hogben , A.Schulte, D.Young and M.Young, Families of graphs with maximum nullity equal to zero forcing number, Spec. Matrices 6 (2018) 56--67.
[4] A. Berman,S. Friedland,L. Hogben,U.G. Rothblum and B.Shader, An upper bound for the minimum rank of a graph, Linear Algebra Appl. 429 (2008), no. 7, 1629--1638.
[5] D. Burgarth, and V. Giovannetti, Full control by locally induced relaxation, Physical Review Letters 99 (2007), no. 10, p100501.
[6] C.J. Edholm, L. Hogben, M. Huynh, J. LaGrange and D.D. Row, Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph, Linear Algebra Appl. 436 (2012), no. 12, 4352--4372.
[7] L. Eroh, C.X. Kang and E. Yi, A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs, Acta Math. Sin. (Engl. Ser.) 33 (2017), no. 6, 731--747.
[8] L. Hogben, M.Huynh, N. Kingsley, S.Meyer S. Walker and M. Young, Propagation time for zero forcing on a graph, Discrete Appl. Math. 160 (2012), no. 13, 1994--2005.
[9] F.Ramezani, E. and Vatandoost, Domination and Signed Domination Number of Cayley Graphs, Iran. J. Math. Sci. Inform. 14 (2019), no. 1, 35--42.
[10] S.Severini, Nondiscriminatory propagation on trees, J. Phys. A 41 (2008), no. 48, p.482002.
[11] E. Vatandoost and Y. Golkhandy Pour, On the zero forcing number of some Cayley graphs, Algebraic Structures and Their Applications 4 (2017), no. 2, 15--25.
[12] E.Vatandoost, F. Ramezani and S. Alikhani, On the zero forcing number of generalized Sierpinski graphs, Trans. Comb. 6 (2019), no. 1, 41--50.