betaFeedback

WorksMathematics

Zero forcing is not unimodal

Abstract

The zero forcing polynomial of a graph counts the number of distinct zero forcing sets of every possible size. In 2018, Boyer et al. asked whether the zero forcing polynomial is always unimodal, and provided some evidence that it is. We answer this question by constructing an infinite family of graphs whose zero forcing polynomials are not unimodal. Our construction also shows that the graph polynomials associated with connected forcing and total forcing are also not unimodal in general.

Introduction

Given a simple graph GG each of whose vertices is initially colored blue or white, the zero forcing color change rule states that a blue vertex with exactly one white neighbor causes (or forces) that neighbor to become blue. The closure of a set SS of blue vertices, denoted cl(S)cl(S), is the set of blue vertices obtained after the color change rule is applied iteratively until no more color changes are possible. SS is a zero forcing set of G=(V,E)G=(V,E) if cl(S)=Vcl(S)=V. Z(G)Z(G) denotes the minimum cardinality of a zero forcing set and z(G;i)z(G;i) denotes the number of zero forcing sets of GG of size ii.

Zero forcing was independently introduced in several contexts [1, 8, 10] and has been widely studied. See the monograph [7] for a comprehensive survey of results related to zero forcing. Numerous variants of zero forcing obtained by modifying the color change rule or by adding certain restrictions to the structure of a zero forcing set have also been studied. For example, connected forcing requires the zero forcing set to induce a connected subgraph [5], and total forcing requires the zero forcing set to induce a graph with no isolated vertices [6].

The zero forcing polynomial of a graph GG on nn vertices is defined as

Z(G;x)=∑i=1nz(G;i)xi.(1)\mathcal{Z}(G;x)=\sum_{i=1}^{n}z(G;i)x^i. \tag*{(1)}

In [3], the authors asked whether the zero forcing polynomial of every graph is unimodal (i.e., whether there is always some i∗∈{1,…,n}i^* \in\{1,\ldots,n\} such that z(G;1)≤⋯≤z(G;i∗)≥⋯≥z(G;n)z(G;1) \le\cdots\le z(G;i^*) \ge\cdots\ge z(G;n)). They showed that the first half of the coefficients are always non-decreasing, i.e., that z(G;i)≤z(G;i+1)z(G;i) \le z(G;i+1) for 1≤i<n21 \le i < \frac{n}{2}. They also showed that the zero forcing polynomials of several families of graphs including paths, cycles, complete graphs, and complete multipartite graphs are unimodal. Thus, it seemed plausible that the answer to the question is affirmative. In this note, we settle this question by constructing an infinite family of graphs whose zero forcing polynomials are not unimodal. Our construction also shows that the graph polynomials associated with connected forcing and total forcing (respectively denoted Zc(G;x)\mathcal{Z}_c(G;x) and Zt(G;x)\mathcal{Z}_t(G;x), and defined analogously to (1)) are also not unimodal in general.

Preliminaries

A simple graph G=(V,E)G=(V,E) consists of a vertex set VV and an edge set EE of two-element subsets of VV. The order of GG is denoted by n=∣V∣n=|V|. Two vertices v,w∈Vv,w\in V are adjacent, or neighbors, if {v,w}∈E\{v,w\}\in E. The neighborhood of v∈Vv\in V, denoted N(v)N(v), is the set of all vertices which are adjacent to vv. The degree of v∈Vv\in V is deg⁡(v)=∣N(v)∣\deg(v)=|N(v)|. An isolated vertex is a vertex that is not adjacent to any other vertex, and a universal vertex is a vertex that is adjacent to all other vertices. Given S⊂VS\subset V, the induced subgraph G[S]G[S] is the subgraph of GG whose vertex set is SS and whose edge set consists of all edges of GG which have both endpoints in SS.

The complete graph on nn vertices is denoted by KnK_n and the empty graph on nn vertices is denoted by Kn‾\overline{K_n}. The join of disjoint graphs G1G_1 and G2G_2, denoted G1∨G2G_1\vee G_2, is the graph obtained by adding an edge between every vertex of G1G_1 and every vertex of G2G_2. For other graph theoretic terminology and definitions, we refer the reader to [9].

Two distinct vertices uu and vv in GG are twins if N(u)∖{v}=N(v)∖{u}N(u)\setminus\{v\}=N(v)\setminus\{u\}, i.e., uu and vv have identical neighborhoods outside {u,v}\{u,v\}. A fort of a graph G=(V,E)G=(V,E) is a non-empty set F⊂VF\subset V such that no vertex outside FF is adjacent to exactly one vertex in FF. It was shown in [4] that every zero forcing set of a graph intersects every fort of the graph. Since each pair of twin vertices is a fort, it follows that every zero forcing set intersects every pair of twin vertices. This can be generalized to larger sets of pairwise twins as follows.

Observation 1. Let G=(V,E)G=(V,E) be a graph and S⊂VS\subset V be a set such that every pair of vertices in SS are twins. Then, every zero forcing set of GG contains all or all-but-one vertices of SS.

Main result

Definition 1. Let HH be the graph shown in Figure 1, with vertices labeled as in the figure. Let A={a1,a2,a3}A=\{a_1,a_2,a_3\}, B={b1,b2}B=\{b_1,b_2\}, C={c1,c2}C=\{c_1,c_2\}, D={d1,d2,d3}D=\{d_1,d_2,d_3\} be a partition of the vertices of HH.

Figure 1. The graph HH.

Definition 2. Let Gp,q,r=H∨K‾p∨K‾q∨KrG_{p,q,r}=H\vee\overline{K}_p\vee\overline{K}_q\vee K_r. Let PP, QQ, and RR respectively denote the vertex sets of the copies of K‾p\overline{K}_p, K‾q\overline{K}_q and KrK_r used in the construction of Gp,q,rG_{p,q,r}, and let H′=P∪Q∪RH'=P\cup Q\cup R. Let Gt=Gt,t,tG_t=G_{t,t,t} and let n=10+3tn=10+3t denote the order of GtG_t.

Example 1. The graph G2G_2 is shown in Figure 2.

Figure 2. The graph G2G_2.

Theorem 1. For t≥2t\ge2, Z(Gt;x)=xn+(10+3t)xn−1+(37+30t+3t2)xn−2+(60+99t)xn−3+(36+108t)xn−4Z(G_t;x)=x^n+(10+3t)x^{n-1}+(37+30t+3t^2)x^{n-2}+(60+99t)x^{n-3}+(36+108t)x^{n-4}.

Proof. Let SS be an arbitrary zero forcing set of GtG_t. Let XX be any one of the sets AA, BB, CC, DD, PP, QQ, RR that partition the vertices of GtG_t according to Definitions 1 and 2. By construction, every pair of vertices x1,x2∈Xx_1, x_2 \in X are twins. Thus, by Observation 1, SS contains either all or all-but-one vertices of XX. Let s=∣H′∖S∣s = |H' \setminus S| be the number of vertices of H′H' that are not in SS. Since SS can exclude at most one vertex from each of PP, QQ, and RR, it follows that s∈{3,2,1,0}s \in\{3,2,1,0\}. We examine each of these cases separately.

Case 1: s=3s = 3. This means SS excludes exactly one vertex from each of PP, QQ, and RR. However, this implies that no vertex can perform the first force, since every vertex in GtG_t would be adjacent to at least two white vertices. Thus, this case cannot occur.

Case 2: s=2s = 2. If SS excludes any vertex of HH in addition to the two vertices in H′H', then again every vertex in GtG_t would be adjacent to at least two white vertices and no vertex could perform the first force. Thus, if s=2s = 2, it follows that SS must include every vertex of HH. On the other hand, any set SS that excludes exactly two vertices uu, v∈H′v \in H' (each of which belongs to a different set among PP, QQ, RR) and includes every other vertex of GtG_t is a zero forcing set. To see why, note that by Pigeonhole Principle, (P∪Q)∩{u,v}≠∅(P \cup Q) \cap\{u,v\} \ne\varnothing. Without loss of generality, suppose u∈Pu \in P and let ww be another vertex in PP. Then, ww can force vv and vv can force uu.

Case 3: s=1s = 1. Suppose for contradiction that in addition to the vertex in H′H', SS also excludes a vertex in BB and a vertex in CC. Then, every vertex in GtG_t would be adjacent to at least two white vertices and no vertex could perform the first force. Thus, if s=1s = 1, SS cannot exclude a vertex from both BB and CC. On the other hand, any set SS that excludes exactly one vertex u∈H′u \in H', excludes at most one vertex from each of AA, BB, CC, and DD, and does not simultaneously exclude a vertex from both BB and CC, is a zero forcing set. To see why, suppose without loss of generality that SS either excludes some (possibly non-proper) subset of {u,a1,b1,d1}\{u,a_1,b_1,d_1\}, or of {u,a1,c1,d1}\{u,a_1,c_1,d_1\}. In the first case, d2d_2 can force uu in the first timestep, then a2a_2 can force b1b_1, then b1b_1 can force a1a_1, and then c1c_1 can force d1d_1 (if a1a_1 and/or b1b_1 and/or d1d_1 do not already belong to SS). In the second case, a2a_2 can force uu in the first timestep, then c2c_2 can force d1d_1, then d1d_1 can force c1c_1, and then b1b_1 can force a1a_1 (if a1a_1 and/or c1c_1 and/or d1d_1 do not already belong to SS).

Case 4: s=0s = 0. This means SS includes every vertex in H′H' and excludes at most one vertex from each of AA, BB, CC, and DD. Any such set is a zero forcing set. To see why, suppose without loss of generality that SS excludes some (possibly non-proper) subset of the vertices {a1,b1,c1,d1}\{a_1,b_1,c_1,d_1\}. In the first timestep, a2a_2 can force b1b_1 and d2d_2 can force c1c_1 (if b1b_1 and/or c1c_1 do not already belong to SS). Then, b1b_1 can force a1a_1 and c1c_1 can force d1d_1 (if a1a_1 and/or d1d_1 do not already belong to SS).

Since the cases above hold for any zero forcing set, they also hold for a minimum zero forcing set. Thus, a minimum zero forcing set can exclude at most 4 vertices of GtG_t, and so Z(Gt)=n−4Z(G_t) = n - 4.

We will now count z(Gt;i)z(G_t;i) for each i∈{n−4,…,n}i \in\{n-4,\ldots,n\}. Clearly, z(Gt;n)=1z(G_t;n) = 1. Since GtG_t is connected, it is also clear that z(Gt;n−1)=n=10+3tz(G_t;n-1) = n = 10 + 3t. To count z(Gt;n−2)z(G_t;n-2), note that there are three possibilities:

  • Both of the excluded vertices are in HH. By Case 4, the excluded vertices can be in any of the pairs of sets (A,B)(A,B), (A,C)(A,C), (A,D)(A,D), (B,C)(B,C), (B,D)(B,D), (C,D)(C,D), which respectively yields 3⋅2+3⋅2+3⋅3+2⋅2+2⋅3+2⋅3=373 \cdot2 + 3 \cdot2 + 3 \cdot3 + 2 \cdot2 + 2 \cdot3 + 2 \cdot3 = 37 distinct zero forcing sets.

  • One of the excluded vertices is in HH and the other is in H′H'. Since there is only a single

excluded vertex in HH, by Case 3 the excluded vertices can be in any of the pairs of sets (A,H′),(B,H′),(C,H′),(D,H′)(A,H'),(B,H'),(C,H'),(D,H'), which respectively yields 3⋅3t+2⋅3t+2⋅3t+3⋅3t=30t3\cdot3t+2\cdot3t+2\cdot3t+3\cdot3t=30t distinct zero forcing sets.

  • Both of the excluded vertices are in H′H'. Since there are no excluded vertices in HH, by Case 2 the excluded vertices can be in any of the pairs of sets (P,Q),(P,R),(Q,R)(P,Q),(P,R),(Q,R), which respectively yields t⋅t+t⋅t+t⋅t=3t2t\cdot t+t\cdot t+t\cdot t=3t^2 distinct zero forcing sets.

Thus, in total z(Gt;n−2)=37+30t+3t2z(G_t;n-2)=37+30t+3t^2. Similarly, to count z(Gt;n−3)z(G_t;n-3), there are two possibilities:

  • All three of the excluded vertices are in HH. By Case 4, the excluded vertices can be in any of the triples of sets (A,B,C),(A,B,D),(A,C,D),(B,C,D)(A,B,C),(A,B,D),(A,C,D),(B,C,D), which respectively yields 3⋅2⋅2+3⋅2⋅3+3⋅2⋅3+2⋅2⋅3=603\cdot2\cdot2+3\cdot2\cdot3+3\cdot2\cdot3+2\cdot2\cdot3=60 distinct zero forcing sets.

  • Two of the excluded vertices are in HH and the third is in H′H'. By Case 3, the excluded vertices can be in any of the triples of sets (A,B,H′),(A,C,H′),(A,D,H′),(B,D,H′),(C,D,H′)(A,B,H'),(A,C,H'),(A,D,H'),(B,D,H'),(C,D,H'), which respectively yields 3⋅2⋅3t+3⋅2⋅3t+3⋅3⋅3t+2⋅3⋅3t+2⋅3⋅3t=99t3\cdot2\cdot3t+3\cdot2\cdot3t+3\cdot3\cdot3t+2\cdot3\cdot3t+2\cdot3\cdot3t=99t distinct zero forcing sets.

Note that it is not possible for two or three of the excluded vertices to be in H′H' by Cases 2 and 1, respectively. Thus, in total z(Gt;n−3)=60+99tz(G_t;n-3)=60+99t. Finally, to count z(Gt;n−4)z(G_t;n-4), there are again two possibilities:

  • All four of the excluded vertices are in HH, with one in each of the sets A,B,C,DA,B,C,D. This yields 3⋅2⋅2⋅3=363\cdot2\cdot2\cdot3=36 distinct zero forcing sets.

  • Three of the excluded vertices are in HH and the fourth is in H′H'. By Case 3, the excluded vertices can be in any of the triples of sets (A,B,D,H′),(A,C,D,H′)(A,B,D,H'),(A,C,D,H'), which respectively yields 3⋅2⋅3⋅3t+3⋅2⋅3⋅3t=108t3\cdot2\cdot3\cdot3t+3\cdot2\cdot3\cdot3t=108t distinct zero forcing sets.

Again, by Cases 2 and 1, it is not possible for more than one of the excluded vertices to be in H′H'. Thus, in total z(Gt;n−4)=36+108tz(G_t;n-4)=36+108t. Plugging in the above coefficients into (1), we obtain Z(Gt;x)=xn+(10+3t)xn−1+(37+30t+3t2)xn−2+(60+99t)xn−3+(36+108t)xn−4\mathcal{Z}(G_t;x)=x^n+(10+3t)x^{n-1}+(37+30t+3t^2)x^{n-2}+(60+99t)x^{n-3}+(36+108t)x^{n-4}.

Example 2. Z(G2;x)=x16+16x15+109x14+258x13+252x12\mathcal{Z}(G_2;x)=x^{16}+16x^{15}+109x^{14}+258x^{13}+252x^{12}.

Corollary 1. For t≥24t\ge24, Z(Gt;x)\mathcal{Z}(G_t;x) is not unimodal.

Proof. We will show that for t≥24t\ge24, z(Gt,n−4)>z(Gt,n−3)z(G_t,n-4)>z(G_t,n-3) and z(Gt,n−3)<z(Gt,n−2)z(G_t,n-3)<z(G_t,n-2). Indeed, using the coefficients derived in Theorem 1 we have

z(Gt,n−4)−z(Gt,n−3)=(36+108t)−(60+99t)=9t−24>0z(G_t,n-4)-z(G_t,n-3)= (36+108t)-(60+99t)= 9t-24>0

and

z(Gt,n−2)−z(Gt,n−3)=(37+30t+3t2)−(60+99t)=3(t−24)2+75(t−24)+49>0.z(G_t,n-2)-z(G_t,n-3)= (37+30t+3t^2)-(60+99t)= 3(t-24)^2+75(t-24)+49>0.

Example 3. G24G_{24} is a graph on 82 vertices with zero forcing polynomial Z(G24;x)=x82+82x81+2485x80+2436x79+2628x78\mathcal{Z}(G_{24};x)=x^{82}+82x^{81}+2485x^{80}+2436x^{79}+2628x^{78}, which is not unimodal.

Corollary 2. For t≥24t \ge24, Zc(Gt;x)\mathcal{Z}_{c}(G_t;x) and Zt(Gt;x)\mathcal{Z}_{t}(G_t;x) are not unimodal.

Proof. As shown in the proof of Theorem 1, every zero forcing set of GtG_t contains either all or all-but-one vertices of RR. Since ∣R∣=t≥24|R|=t \ge24 it follows that every zero forcing set SS of GtG_t includes a vertex of RR which is a universal vertex, and hence that SS induces a connected subgraph with no isolated vertices. On the other hand, every connected or total forcing set of a graph GG must also be a zero forcing set of GG. Thus, SS is a zero forcing set of GtG_t if and only if SS is a connected forcing set of GtG_t if and only if SS is a total forcing set of GtG_t. It follows that Z(Gt;x)=Zc(Gt;x)=Zt(Gt;x)\mathcal{Z}(G_t;x)=\mathcal{Z}_{c}(G_t;x)=\mathcal{Z}_{t}(G_t;x), and so by Corollary 1, Zc(Gt;x)\mathcal{Z}_{c}(G_t;x) and Zt(Gt;x)\mathcal{Z}_{t}(G_t;x) are not unimodal for t≥24t \ge24.

Conclusion

In this note we showed that the zero forcing polynomial of a graph is in general not unimodal. It would be interesting to explore whether certain graph properties guarantee unimodality or non-unimodality of the zero forcing polynomial. Specifically, we pose the following open question.

Question 1. Is the zero forcing polynomial of a tree always unimodal?

There are smaller graphs than G24G_{24} whose zero forcing polynomials are not unimodal. For example, it can be shown with a similar argument as Theorem 1 that Z(G24,24,23;x)=2592x77+2403x78+2427x79+81x80+x81\mathcal{Z}(G_{24,24,23};x)=2592x^{77}+2403x^{78}+2427x^{79}+81x^{80}+x^{81}. The following remains an open question.

Question 2. What is the smallest graph with a non-unimodal zero forcing polynomial?

Finally, it would be interesting to determine whether non-unimodality of the zero forcing polynomial is rare (e.g., among all graphs of order nn), or whether there are in fact many more examples to be found. Some work in this direction has been initiated in [2].

Question 3. Do almost all graphs have unimodal zero forcing polynomials?

AI Disclosure

Generative AI systems were used during the mathematical investigation and to generate an early draft of the manuscript. The final draft, including all proofs, was rewritten from scratch entirely by humans.

References

  1. [1]AIM Special Work Group. Zero forcing sets and the minimum rank of graphs. Linear Algebra and its Applications, 428(7):1628–1648, 2008.
  2. [2]J. A. Makowsky and V. Rakita. Almost unimodal and real-rooted graph polynomials. European Journal of Combinatorics, 108:103637, 2023.arxiv.org/abs/2102.00268
  3. [3]K. Boyer, B. Brimkov, S. English, D. Ferrero, A. Keller, R. Kirsch, M. Phillips and C. Reinhart. The zero forcing polynomial of a graph. Discrete Applied Mathematics, 258:35–48, 2019.DOI
  4. [4]B. Brimkov, C. C. Fast and I. V. Hicks. Computational approaches for zero forcing and related problems. European Journal of Operational Research, 273(3):889–903, 2019.arxiv.org/abs/1704.02065
  5. [5]B. Brimkov and I. V. Hicks. Complexity and computation of connected zero forcing. Discrete Applied Mathematics, 229:31–45, 2017.arxiv.org/abs/1607.00658
  6. [6]R. Davila and M. A. Henning. Total forcing and zero forcing in claw-free cubic graphs. Graphs and Combinatorics, 34(6):1371–1384, 2018.arxiv.org/abs/1708.05041
  7. [7]L. Hogben, J. C.-H. Lin and B. L. Shader. Inverse problems and zero forcing for graphs. Vol. 270, American Mathematical Society, 2022.DOI
  8. [8]D. Burgarth and V. Giovannetti. Full control by locally induced relaxation. Physical Review Letters, 99(10):100501, 2007.DOI
  9. [9]D. B. West. Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 2001.
  10. [10]B. Yang. Fast-mixed searching and related problems on graphs. Theoretical Computer Science, 507:100–113, 2013.DOI

Paper details

vlnc:W_7wmq5sdm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Generative AI systems

View statement
Looking for related papers…
Contents