ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.729465 J. Algebra Comb. Discrete Appl. 7(2) • 183–193 Received: 9 July 2018 Accepted: 10 October 2019 Journal of Algebra Combinatorics Discrete Structures and Applications Computing the zero forcing number for generalized Petersen graphs∗ Research Article Saeedeh Rashidi, Nosratollah Shajareh Poursalavati, Maryam Tavakkoli 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 → 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 ≥ 10, Z(P(n, 3)) = 8 for n ≥ 12 and Z(P(2k + 1, k)) = 6 for k ≥ 5. 2010 MSC: 05C83, 05C10 Keywords: Zero forcing number, Generalized Petersen graph, Colin de Verdière parameter 1. Introduction Let G = (V,E) be a simple undirected graph. Each vertex is colored either white or black. In such a case we say that G has a coloring and the set of all black vertices is called an initial coloring of G. The color-change rule is defined as follows: if u is a black vertex of G and exactly one neighbor v of u is white, then the color of v changes to black. Given a coloring of G, let A be the set of all black vertices of G. The derived coloring of A, denoted der(A), is the result of applying the color-change rule until no more changes are possible. The zero forcing set for a graph G (ZFS) is an initial coloring Z of G such that der(Z) = G. The zero forcing number Z(G) is the minimum size of all zero forcing sets of G. The concept of zero forcing set indicates one ∗ This work was supported by Mahani Mathematical Research Center, Shahid Bahonar University of Kerman, Kerman, Iran. Saeedeh Rashidi (Corresponding Author), Nosratollah Shajareh Poursalavati, Maryam Tavakkoli; Department of Applied Mathematics, Faculty of Mathematics and Computer, Shahid Bahonar University of Kerman, Kerman, Iran (email: saeedeh.rashidi@uk.ac.ir, salavati@uk.ac.ir, mtavakkoli1362@gmail.com). 183 https://orcid.org/0000-0002-8262-0910 https://orcid.org/0000-0003-0046-0325 https://orcid.org/0000-0002-2863-4799 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 model of propagation in general networks. It was introduced in [4]. the associated terminology has been extended in [5, 7, 11, 12]. For example according to [4] if G is a path, an endpoint of G is the zero forcing set for G. If G is a cycle, each set of two adjacent vertices is a zero forcing set. A contraction of a graph G is the graph obtained by identifying two adjacent vertices of G, and ignoring any loops or multiple edges occurred. A minor of G is a graph obtained by applying a sequence of deletions of edges, deletions of isolated vertices, and contraction of edges. A graph parameter ζ is called minor monotone if for any minor H of G, ζ(H) ≤ ζ(G). Definition 1.1 ([9]). The generalized Petersen graph P(n,k) is defined to be the graph with the vertex set and edge set respectively as follows V (P(n,k)) = {u1, . . . ,un,v1, . . . ,vn} E(P(n,k)) = {uiui+1, uivi, vivi+k : 1 ≤ i ≤ n}. Here, the subscripts are assumed as integers modulo n such that n ≥ 5. Note that, P(n,k) ∼= P(n,n−k). So, we assume n ≥ 2k + 1. P(n,k) is a 3-regular graph with 2n vertices. The generalized Petersen graph has been studied from several points of view, such as: hamiltonicity [1, 3, 15], crossing numbers [13, 14], spectrum [10] and vertex domination [9]. In Section 2, we turn to the zero forcing number of the generalized Petersen graphs. We present an upper bound for Z(P(n,k)). We show that Z(P(n,2)) = 6 for n ≥ 10, Z(P(n,3)) = 8 for n ≥ 12 and Z(P(2k + 1,k)) = 6 for k ≥ 5. In Section 3, we show that Kk,[ n k ] is a minor of P(n,k) (where [x] is the maximum integer not greater than x). Using this, we conclude that: min{k, [ n k ]}+ 1 = µ ( Kk,[ n k ] ) ≤ µ(P(n,k)) ≤ Z(P(n,k)). The graph parameter µ is introduced by Colin de Verdiere in 1990 [6]. It is equal to the maximum nullity among all matrices satisfying several conditions. This conditions are stated in Section 3. It is the first parameter of Colin de Verdiere type parameters. There exist a relation between this parameter and the zero forcing number that we apply it for achieving the upper bound. There exists a comparison between the zero forcing sets and dynamic monopolies in the last section. Note that, in all figures of this paper the vertex vi(ui) is indicated by [i]v([i]u). 2. Upper bounds and equalities for Z(P(n, k)) In the following theorem, we obtain an upper bound for Z(P(n,k)), where k - n. Theorem 2.1. If n = rk + s, then Z(P(n,k)) ≤ r(s + 2), where 1 ≤ s ≤ k −1, r,s ∈ N. Proof. Let A = {u1,u2, · · · ,us+2,u1+k,u2+k, · · · ,us+2+k, · · · ,u1+(r−1)k,u2+(r−1)k, · · · ,us+2+(r−1)k} be an initial coloring of P(n,k). The following vertices change to black by the color-change rule: {v2, . . . ,vs+1,v2+k, . . . ,vs+1+k, . . . ,v2+(r−1)k, . . . ,vs+1+(r−1)k}. Since, two neighbors of the vertices uj, 2 + ik ≤ j ≤ s + 1 + ik for 0 ≤ i ≤ r − 1 are black and the only white neighbor of them is vj. We also show that the vertices {v1,v1+k, . . . ,v1+(r−1)k} are in der(A). Note that s + 1 + (r −1)k = s + rk + 1−k = n + 1−k ≡ 1−k (mod(n)). We have the following adjacency: 184 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 The vertex v1 is the only white neighbor of the black vertex vs+1+(r−1)k and the vertex vs+1+(r−1)k forces it. The vertex vk+1 is the only white neighbor of the black vertex v1 and the vertex v1 forces it. The vertex v1+(r−1)k is the only white neighbor of the black vertex v1+(r−2)k and the vertex v1+(r−2)k forces it. Also, the color of the vertices un,uk, . . . ,u(r−1)k,vn,vk, . . . ,v(r−1)k change to black. The vertex un is the only white neighbor of the black vertex u1 and is forced by it. For i = 1, · · · ,r−1, the vertex uik is the only white neighbor of the black vertex uik+1 and is forced by it. The vertex vn is the only white neighbor of the black vertex v(r−1)k+s and is forced by it. The vertex vk is the only white neighbor of the black vertex vn and is forced by it. For i = 2, · · · ,r−1, the vertex vik is the only white neighbor of the black vertex v(i−1)k and is forced by it. Now, for i = 1, . . . ,r: The vertex uik−1 is the only white neighbor of the black vertex uik and is forced by it. Then the vertex vik−1 is the only white neighbor of the black vertex uik−1 and is forced by it. Also for each t < k, it is one counter, we have: The vertex uik−t is the only white neighbor of the black vertex uik−t+1 and is forced by it. the vertex vik−t is the only white neighbor of the black vertex uik−t and is forced by it. This process continues until ik−t = i(k −1) + s + 3 and ui(k−1)+s+3 forced by uik+s+4. Then vi(k−1)+s+2 is the only white neighbor of the black vertex ui(k−1)+s+3 and is forced by it. So, all vertives of graph became black. In the next theorem we obtain an upper bound for Z(P(n,k)). This bound does not depend on n. Theorem 2.2. Z(P(n,k)) ≤ 2k + 2. Proof. Let A = {u1,u2, . . . ,u2k+2} be an initial coloring of P(n,k) (see Figure 1). The vertex vj is the only white neighbor of the black vertex uj for 2 ≤ j ≤ 2k + 1. It is forced by uj. So, vj ∈ der(A). Now the vertex v1 is the only white neighbor of the vertex u1 and is forced by it. Therefore v2k+2 is the only white neighbor of the black vertex vk+2. Hence, the vertices v2, v3,. . . ,v2k+2 are in der(A). We continue by induction. Let m ≥ 2k + 2 and the color of vertices{ um, . . . ,u2,u1 vm, . . . ,v2 have been changed to black. It suffices to show that the color of the vertices um+1 and vm+1 change to black. Note that m ≥ 2k + 2 hence m ≥ m + 1 − 2k ≥ 3. Therefore, the vertex vm+1 is the only white neighbor of the black vertex vm+1−k and um+1 is the only white neighbor of the black vertex um. Corollary 2.3. If n = rk + s, then Z(P(n,k)) ≤ min{r(s + 2),2k + 2}, where 1 ≤ s ≤ k −1. Remark 2.4. In [2] the authors proved that Z(P(15r,2)) = 6 and Z(P(24r,5)) = 12 for all r ≥ 1. Also they proved Theorem 2.2 another way. They obtain the upper bound Z(P(2k + 1,k)) ≤ 6 that we conclude this upper bound from Theorem 2.1 and obtain the equality in Theorem 2.6. Theorem 2.5. If n ≥ 10, then Z(P(n,2)) = 6. Proof. By Theorem 2.2, we have Z(P(n,2)) ≤ 6. Hence it suffices to show that no initial coloring of the graph with five vertices can be a zero forcing set. Let A be such an initial coloring. By checking all of possible cases we show that |der(A)| ≤ 10 < 2n = |P(n,2)|. We have illustrated all cases, unless the trivial or similar ones, in the following figures. In each figure the white vertices are the vertices that will change to black by A. The set A can consist some vertices of type ui or vi. Therefore, the following division is considered. Note that, r vertices can be belong to the inner cycle of generalized peterson graph 185 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 Figure 1. An initial coloring of P(n, k) by 2k + 2 vertices and 5−r vertices must be belong to the outer cycle of it. 1. The set A consists of five v-vertices (r = 5): Note that, the vertex vi and vi+8 are adjacent for n = 10. 2. The set A consists of five u-vertices (r = 0): 186 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 3. The set A consists of four u-vertices and one v-vertex (r = 1): 4. The set A consists of four v-vertices and one u-vertex (r = 4): 5. The set A consists of three u-vertices and two v-vertices (r = 2): 187 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 6. The set A consists of two u-vertices and three v-vertices (r = 3): 188 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 Theorem 2.6. If k ≥ 5, then Z(P(2k + 1,k)) = 6. Proof. By Theorem 2.1, we have Z(P(2k+1,k)) ≤ 6. By the same argument of Theorem 2.5, we show that, no initial coloring A with 5 vertices can be a zero forcing set for P(n,k). The cases are essentially same as Theorem 2.5. 1. The set A consists of five u-vertices: 2. The set A consists of five v-vertices: 3. The set A consists of four u-vertices and one v-vertex: 189 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 4. The set A consists of four v-vertices and one u-vertex: 5. The set A consists of three u-vertices and two v-vertices: 6. The set A consists of two u-vertices and three v-vertices: 190 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 3. Lower bound for Z(P(n, k)) In this section, we obtain a lower bound for Z(P(n,k)). For this aim, we use the graph parameter µ(G). It has a monotonicity property, which proved first by Colin de Verdière in [8]. Definition 3.1. [16] Let G = (V,E) be an undirected graph, assuming (without loss of generality) that V = {1, . . . ,n}. Then parameter µ(G) is the largest corank of any matrix M = (Mi,j) ∈ Rn such that: (M1) for all i,j with i 6= j: Mi,j < 0 if i and j are adjacent and Mi,j = 0 if i and j are nonadjacent; (M2) M has exactly one negative eigenvalue, of multiplicity 1; (M3) there is no nonzero matrix X = (Xi,j) ∈ Rn such that MX = 0 and such that Xi,j = 0 whenever i = j or Mi,j 6= 0. In [6] it is stated that µ(G) ≤ Z(G). Theorem 3.2. [8] If H is a minor of a graph G, then µ(H) ≤ µ(G). This property sometimes described as µ minor-monotone. For instance µ(Kn) = n−1 and for p ≤ q µ(Kp,q) = { p if q ≤ 2 p + 1 if q ≥ 3 See [16] for more details. Definition 3.3. Let G = (V,E) be a simple graph and A,B be none-empty subsets of V (G). We say that A and B are adjacent if there exist vertices x ∈ A and y ∈ B such that xy ∈ E. In such a case we write A ∼ B. Theorem 3.4. If k ≥ 3, then the graph Kk,[ n k ] is a minor of P(n,k). Proof. Let Ai = {u(1+(i−1)k),u2+(i−1)k, . . . ,uk+(i−1)k} for each 1 ≤ i ≤ r = nk . Put Bj = {vj,vj+k, . . . ,vj+(r−1)k} for each 1 ≤ j ≤ k. It is easy to see that each Ai is adjacent to each Bj and Bi is not adjacent to Bj for i 6= j. Now proceed as follows: 1. Delete the edges between the vertices 1 + mku and mku for each 1 ≤ m ≤ r. 2. Contract all the vertices of Ai in the vertex u1+(i−1)k (starting with the vertex uk+(i−1)k and contracting successively). 3. Contract all the vertices of Bj in the vertex vj. 4. Delete all the remaining vertices and their edges. Finally, we achieve the complete bipartite graph Now, we obtain the following lower bound. Corollary 3.5. If k ≥ 3, then min{k, n k }+ 1 ≤ Z(P(n,k)). Theorem 3.6. If n ≥ 12, then Z(P(n,3)) = 8. Proof. Let A be a set of initial black vertices of the graph P(n,3). By Corollary 3.5, 4 ≤ |A|. Let ui be one white vertex on the outer cycle. The color of it can be forced by the vertex ui−1, vertex ui+1 or the vertex vi. 191 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 Assume the vertices u1, · · · ,ui−1 ∈ A, then: 1) If the vertex ui−1 wants to force the vertex ui, then it is necessary that vi−1 ∈ A. 2) If the vertex ui+1 wants to force the vertex ui, then it is necessary that vi+1,ui+1,ui+2 ∈ A. 3) If the vertex vi wants to force the vertex ui, then it is necessary that vi,vi−k,vi+k ∈ A. Therefor the best case for the color-change processing in the vertices of the outer cycle is that the vertex ui−1 forces the vertex ui. So, suppose {u1,u2,u3,u4} ⊆ A. This set can not change the color of all vertices. By a simple argument, we conclude that the set A be {u1,u2,u3 · · · ,u8}. 4. A comparison between zero forcing sets and dynamic monop- olies In the last section, we compare the zero forcing sets with another propagation concept of graph theory. This concept is dynamic monopoly. It is studied by Zaker in [17]. Definition 4.1. [17] By a threshold assignment for the vertices of G we mean any function τ : V (G) → N ∪{0}. A subset of vertices D is said to be a τ-dynamic monopoly of G or simply τ-dynamo of G, if for some nonnegative integer k, the vertices of G can be partitioned into subsets D0,D1, ...,Dk such that D0 = D and for any i,1 ≤ i ≤ k, the set Di consists of all vertices v which has at least τ(v) neighbors in D0 ∪ . . .∪Di−1. Denote the smallest size of any τ-dynamo of G by dyn(G). It is obvious that each ZFS is a 1-dynamo. For τ = 1, there does not exist any resistant subgraph. So, each subgraph can be a candidate for a dynamo of graph. [17] A resistant subgraph of G means each subgraph K such that for each vertex v ∈ K one has dK(v) ≥ dG(v)t(v) + 1, where dG(v) is the degree of v in G. Zaker proved that each dynamo of graph does not contain any resistant subgraph of it [17]. So, it is satisfy for the ZFS. Example 4.2. We know Z(Kn) = n− 1 and Z(Pn) = 1. The ZFS of complete graph Kn and path Pn are 1-dynamo too. For the complete graph K4, dyn(K4) 6= Z(K4). It is an interesting question that for what graphs there exist this equality. In this example the subsets D0 and D1 are ZFS. Figure 2. Z(K4) = 3 and dyn(K4) = 1 If we consider D0 = {A} and D1 = {B,C,D}. Then the subset D0 is a dynamo and it is not a ZFS. There exists another question. A dynamo under what condition is a ZFS? The following lemma states this conditions. Lemma 4.3. Consider one Dynamo as D0,D1, ...,Dk. If for each vertex u ∈ Di+1 there exist a vertex v ∈ Di such that N(v)−{u}⊆ (D0 ∪D1 ∪·· ·∪Di), then that dynamo is a ZFS. There exists one lower bound for Z(G) which is obtained from the following results about dynamos. Theorem 4.4. [17] Let D be a dynamic monopoly of size k in G. Set H = G\D and let tmax be the maximum threshold among the vertices of H. Then: 1) ∑ v∈H t(v) ≤ |E(G)|− |E(G[D])|− δ(G) + tmax. 2) ∑ v∈H t(v) ≤ |E(G)| provided that t(v) ≤ dG(v) for any vertex v ∈ H. 192 S. Rashidi et al. / J. Algebra Comb. Discrete Appl. 7(2) (2020) 183–193 We know that each ZFS is a 1-dynamo. So, we have the following corollary. Corollary 4.5. Let G be a graph with 1 ≤ δ(G), then: 1) |G|− |E(G)|+ |E(G[ZFS])|+ δ −1 ≤ Z(G). 2) |G|− |E(G)| ≤ Z(G) Also, Corollary 2 from [17] confirms the second inequality. This first bound is equality for some graphs. For example, let G be a complete graph Kn. So |G| − |E(G)| + |E(G[ZFS])| + δ − 1 = n − (n)(n−1) 2 + (n−1)(n−2) 2 + (n−1)−1 = n−1 and Z(Kn) = n−1. Also, it is equality for path (Z(Pt) = 1). The characterization of all graphs that satisfy this bound will be interesting. 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. Cioabă, D. Cvetković, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanović, 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. Stănică, The spectrum of generalized Petersen graphs, Australian Journal of Combina- torics, 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. 193 https://doi.org/10.1016/0095-8956(83)90042-4 https://doi.org/10.1016/0095-8956(83)90042-4 https://doi.org/10.1515/spma-2018-0006 https://doi.org/10.1515/spma-2018-0006 https://doi.org/10.1016/0095-8956(78)90019-9 https://doi.org/10.1016/0095-8956(78)90019-9 https://doi.org/10.1016/j.laa.2007.10.009 https://doi.org/10.1016/j.laa.2007.10.009 https://doi.org/10.1016/j.laa.2007.10.009 https://doi.org/10.1016/j.laa.2007.10.009 https://doi.org/10.1016/j.laa.2010.03.008 https://doi.org/10.1016/j.laa.2010.03.008 https://doi.org/10.1002/jgt.21637 https://doi.org/10.1002/jgt.21637 https://doi.org/10.1002/jgt.21637 https://doi.org/10.13001/1081-3810.1300 https://doi.org/10.13001/1081-3810.1300 https://doi.org/10.13001/1081-3810.1300 https://doi.org/10.1016/0095-8956(90)90093-F https://doi.org/10.1016/0095-8956(90)90093-F https://doi.org/10.1016/j.disc.2009.01.018 https://doi.org/10.1016/j.disc.2009.01.018 https://doi.org/10.1016/j.laa.2009.05.003 https://doi.org/10.1016/j.laa.2010.01.001 https://doi.org/10.1016/j.laa.2010.01.001 https://doi.org/10.1016/0012-365X(92)90453-M https://doi.org/10.1016/0012-365X(92)90453-M https://doi.org/10.1016/j.disc.2004.07.036 https://doi.org/10.1016/j.disc.2004.07.036 https://doi.org/10.1016/0095-8956(89)90064-6 https://doi.org/10.1016/0095-8956(89)90064-6 https://doi.org/10.1016/j.disc.2011.11.038 https://doi.org/10.1016/j.disc.2011.11.038 Introduction Upper bounds and equalities for Z(P(n,k)) Lower bound for Z(P(n,k)) A comparison between zero forcing sets and dynamic monopolies References