Vatandoost, E., Golkhandy Pour, Y. (2017). On the zero forcing number of some Cayley graphs. Algebraic Structures and Their Applications, 4(2), 15-25. doi: 10.29252/asta.4.2.15

Ebrahim Vatandoost; Yasser Golkhandy Pour. "On the zero forcing number of some Cayley graphs". Algebraic Structures and Their Applications, 4, 2, 2017, 15-25. doi: 10.29252/asta.4.2.15

Vatandoost, E., Golkhandy Pour, Y. (2017). 'On the zero forcing number of some Cayley graphs', Algebraic Structures and Their Applications, 4(2), pp. 15-25. doi: 10.29252/asta.4.2.15

Vatandoost, E., Golkhandy Pour, Y. On the zero forcing number of some Cayley graphs. Algebraic Structures and Their Applications, 2017; 4(2): 15-25. doi: 10.29252/asta.4.2.15

^{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(D_{2n},S))=2|S|-2, where D_{2n} is dihedral group of order 2n and S={a, a^{3}, ... , a^{2k-1}, b}. Also, we obtain Z(Cay(G,S)), where G=< a> is a cyclic group of even order n and S={a^{i} : 1≤ i≤ n and i is odd}, S={a^{i} :1≤ i≤ n and i is odd}\{a^{k},a^{-k}} or |S|=3.

[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. Cioab˘ a, D.

Cvetkovi´ c, S.M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova,

I. Sciriha, W. So, D. Stevanovi´ c, 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 Ap

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