On the zero forcing number of some Cayley graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, Faculty of Sciences, Imam Khomeini International University, Qazvin, Iran

2 Department of Mathematics, Faculty of sciences, Imam Khomeini International University, Qazvin, Iran

Abstract

‎Let Γa be a graph whose each vertex is colored either white or black‎. ‎If u is a black vertex of Γ such that exactly one neighbor‎ ‎v of u is white‎, ‎then u changes the color of v to black‎. ‎A zero forcing set for a Γ graph is a subset of vertices Z\subseteq V(Γ) such that‎ if initially the vertices in Z are colored black and the remaining vertices are colored white‎, ‎then Z changes the color of all vertices Γ in to black‎. ‎The zero forcing number of Γ is the minimum of |Z| over all zero forcing sets for Γ and is denoted by Z(Γ)‎. In this paper‎, ‎we consider the zero forcing number of some families of Cayley graphs‎. ‎In this regard‎, ‎we show that Z(Cay(D2n,S))=2|S|-2‎, ‎where D2n is dihedral group of order 2n and S={a‎, ‎a3‎, ‎... ‎, ‎a2k-1‎, ‎b}. ‎Also‎, ‎we obtain Z(Cay(G,S))‎, ‎where G=< a> is a cyclic group of even order n and S={ai :‎ 1≤ i≤ n‎ and i is odd}‎, ‎S={ai‎ :‎1≤ i≤ n‎ and i is odd}\{ak,a-k} or |S|=3‎.

Keywords

References

[1] A. Abdollahi, E. Vatandoost, Which Cayley graphs are integral?, Electron. J. Combin., 16 (1) (2009), pp. 1-17.
[2] 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 (2008), pp. 1628-1648.
[3] F. Barioli, W. Barrett, S.M. Fallat, H.T. Hall, L. Hogben, B. Shader, P.V. Driessche, and H.V. Holst, Parameters related to tree-width, zero forcing, and maximum nullity of a graph, Journal of Graph Theory, 72(2) (2013), pp. 146-177.
[4] F. Barioli and S. Fallat, On the minimum rank of the join of graphs and decomposable graphs, Linear Algebra and its Applications, 421 (2007), pp. 252-263.
[5] F. Barioli, S. Fallat, and L. Hogben, A variant on the graph parameters of Colin de Verdi` ere: Implications to the minimum rank of graphs, Electronic Journal of Linear Algebra, 13 (2005), pp. 387-404.
[6] A. Berman, S. Friedland, L. Hogben, U.G. Rothblum, B. Shader, An upper bound for the minimum rank of a graph, Linear Algebra and its Application, 429(2008), 1629-1638.
[7] R. Davila, F. Kenter, Bounds for the Zero-Forcing Number of Graphs with Large Girth, Theory and Applications of Graphs, 2(2) (2015), Article 1, pp. 1-8.
 [8] C.J. Edholm, L. Hogben, M. Huynh, J. LaGrange, D.D. Row, Vertex and edge spread of the zero forcing number, maximum nullity, and minimum rank of a graph, Linear Algebra and its Applications 436 (2012), pp. 4352-4372.
[9] S.M. Fallat and L. Hogben, The minimum rank of symmetric matrices described by a graph: A survey, Linear Algebra and its Applications, 426 (2007), pp. 558-582.
[10] M. Gentner, L.D. Penso, D. Rautenbach, U.S. Souza, Extremal Values and Bounds for the Zero Forcing Number, Discrete Applied Mathematics, 214 (2016), pp. 196-200.
[11] M. Gentner and D. Rautenbach, Some Bounds on the Zero Forcing Number of a Graph, arXiv:1608.00747v1.
[12] L. Hogben, Orthogonal representations, minimum rank, and graph complements, Linear Algebra and its Applications, 428 (2008), pp. 2560-2568.
[13] C.R. Johnson, R. Loewy, and P.A. Smith, The graphs for which the maximum multiplicity of an eigenvalue is two, Linear and Multilinear Algebra, 57 (2007), pp. 713-736.
[14] D.D. Row, A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra and its Applications, 436 (2012), pp. 4423-4432.
Algebraic Structures and Their Applications
Volume 4, Issue 2
November 2017
Pages 15-25

Files

Share

How to cite

Statistics