In this paper
AbstractIntroductionPreliminariesMain resultConclusionAI DisclosureReferencesWorksMathematics
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 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 of blue vertices, denoted , is the set of blue vertices obtained after the color change rule is applied iteratively until no more color changes are possible. is a zero forcing set of if . denotes the minimum cardinality of a zero forcing set and denotes the number of zero forcing sets of of size .
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 on vertices is defined as
In [3], the authors asked whether the zero forcing polynomial of every graph is unimodal (i.e., whether there is always some such that ). They showed that the first half of the coefficients are always non-decreasing, i.e., that for . 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 and , and defined analogously to (1)) are also not unimodal in general.
Preliminaries
A simple graph consists of a vertex set and an edge set of two-element subsets of . The order of is denoted by . Two vertices are adjacent, or neighbors, if . The neighborhood of , denoted , is the set of all vertices which are adjacent to . The degree of is . 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 , the induced subgraph is the subgraph of whose vertex set is and whose edge set consists of all edges of which have both endpoints in .
The complete graph on vertices is denoted by and the empty graph on vertices is denoted by . The join of disjoint graphs and , denoted , is the graph obtained by adding an edge between every vertex of and every vertex of . For other graph theoretic terminology and definitions, we refer the reader to [9].
Two distinct vertices and in are twins if , i.e., and have identical neighborhoods outside . A fort of a graph is a non-empty set such that no vertex outside is adjacent to exactly one vertex in . 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 be a graph and be a set such that every pair of vertices in are twins. Then, every zero forcing set of contains all or all-but-one vertices of .
Main result
Definition 1. Let be the graph shown in Figure 1, with vertices labeled as in the figure. Let , , , be a partition of the vertices of .
Figure 1. The graph .
Definition 2. Let . Let , , and respectively denote the vertex sets of the copies of , and used in the construction of , and let . Let and let denote the order of .
Example 1. The graph is shown in Figure 2.
Figure 2. The graph .
Theorem 1. For , .
Proof. Let be an arbitrary zero forcing set of . Let be any one of the sets , , , , , , that partition the vertices of according to Definitions 1 and 2. By construction, every pair of vertices are twins. Thus, by Observation 1, contains either all or all-but-one vertices of . Let be the number of vertices of that are not in . Since can exclude at most one vertex from each of , , and , it follows that . We examine each of these cases separately.
Case 1: . This means excludes exactly one vertex from each of , , and . However, this implies that no vertex can perform the first force, since every vertex in would be adjacent to at least two white vertices. Thus, this case cannot occur.
Case 2: . If excludes any vertex of in addition to the two vertices in , then again every vertex in would be adjacent to at least two white vertices and no vertex could perform the first force. Thus, if , it follows that must include every vertex of . On the other hand, any set that excludes exactly two vertices , (each of which belongs to a different set among , , ) and includes every other vertex of is a zero forcing set. To see why, note that by Pigeonhole Principle, . Without loss of generality, suppose and let be another vertex in . Then, can force and can force .
Case 3: . Suppose for contradiction that in addition to the vertex in , also excludes a vertex in and a vertex in . Then, every vertex in would be adjacent to at least two white vertices and no vertex could perform the first force. Thus, if , cannot exclude a vertex from both and . On the other hand, any set that excludes exactly one vertex , excludes at most one vertex from each of , , , and , and does not simultaneously exclude a vertex from both and , is a zero forcing set. To see why, suppose without loss of generality that either excludes some (possibly non-proper) subset of , or of . In the first case, can force in the first timestep, then can force , then can force , and then can force (if and/or and/or do not already belong to ). In the second case, can force in the first timestep, then can force , then can force , and then can force (if and/or and/or do not already belong to ).
Case 4: . This means includes every vertex in and excludes at most one vertex from each of , , , and . Any such set is a zero forcing set. To see why, suppose without loss of generality that excludes some (possibly non-proper) subset of the vertices . In the first timestep, can force and can force (if and/or do not already belong to ). Then, can force and can force (if and/or do not already belong to ).
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 , and so .
We will now count for each . Clearly, . Since is connected, it is also clear that . To count , note that there are three possibilities:
Both of the excluded vertices are in . By Case 4, the excluded vertices can be in any of the pairs of sets , , , , , , which respectively yields distinct zero forcing sets.
One of the excluded vertices is in and the other is in . Since there is only a single
excluded vertex in , by Case 3 the excluded vertices can be in any of the pairs of sets , which respectively yields distinct zero forcing sets.
Both of the excluded vertices are in . Since there are no excluded vertices in , by Case 2 the excluded vertices can be in any of the pairs of sets , which respectively yields distinct zero forcing sets.
Thus, in total . Similarly, to count , there are two possibilities:
All three of the excluded vertices are in . By Case 4, the excluded vertices can be in any of the triples of sets , which respectively yields distinct zero forcing sets.
Two of the excluded vertices are in and the third is in . By Case 3, the excluded vertices can be in any of the triples of sets , which respectively yields distinct zero forcing sets.
Note that it is not possible for two or three of the excluded vertices to be in by Cases 2 and 1, respectively. Thus, in total . Finally, to count , there are again two possibilities:
All four of the excluded vertices are in , with one in each of the sets . This yields distinct zero forcing sets.
Three of the excluded vertices are in and the fourth is in . By Case 3, the excluded vertices can be in any of the triples of sets , which respectively yields 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 . Thus, in total . Plugging in the above coefficients into (1), we obtain .
Example 2. .
Corollary 1. For , is not unimodal.
Proof. We will show that for , and . Indeed, using the coefficients derived in Theorem 1 we have
and
Example 3. is a graph on 82 vertices with zero forcing polynomial , which is not unimodal.
Corollary 2. For , and are not unimodal.
Proof. As shown in the proof of Theorem 1, every zero forcing set of contains either all or all-but-one vertices of . Since it follows that every zero forcing set of includes a vertex of which is a universal vertex, and hence that induces a connected subgraph with no isolated vertices. On the other hand, every connected or total forcing set of a graph must also be a zero forcing set of . Thus, is a zero forcing set of if and only if is a connected forcing set of if and only if is a total forcing set of . It follows that , and so by Corollary 1, and are not unimodal for .
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 whose zero forcing polynomials are not unimodal. For example, it can be shown with a similar argument as Theorem 1 that . 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 ), 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]AIM Special Work Group. Zero forcing sets and the minimum rank of graphs. Linear Algebra and its Applications, 428(7):1628–1648, 2008.
- [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]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]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]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]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]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]D. Burgarth and V. Giovannetti. Full control by locally induced relaxation. Physical Review Letters, 99(10):100501, 2007.DOI
- [9]D. B. West. Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 2001.
- [10]B. Yang. Fast-mixed searching and related problems on graphs. Theoretical Computer Science, 507:100–113, 2013.DOI

