The smallest graph patterns that rule out a bounded complementary zero-forcing parameter cannot grow without limit. For every integer bound k of at least 1, a minimal forbidden graph has no more than 2k + 2 vertices, and the associated forbidden family is finite for each fixed k.
The study concerns an abstract graph color-change game, not an empirical sample of people, animals or laboratory systems. Some vertices start blue and others white. A blue vertex can turn a white vertex blue when that vertex is its only white neighbor. The move is denoted x → y. The paper studies the complementary parameter mz(G), which is the number of vertices in G minus its zero-forcing number.
The parameter is monotone under induced subgraphs, meaning it cannot become larger when a graph is reduced by selecting vertices and keeping all edges between them. In notation, if H is an induced subgraph of G, mz(H) is no larger than mz(G). That turns forbidden patterns into a test for larger graphs: if a prohibited pattern appears as an induced subgraph, the larger graph is excluded as well.
A complete answer at the threshold of three
At the threshold mz at most 3, a brute-force search found all minimal forbidden graphs. The set is shown in Figure 2, and the target class consists of graphs that contain none of those patterns. The supplied text does not spell out the individual drawings, so the result is a complete figure-based set rather than a list that can be reconstructed from the text alone.
Forests, graphs with no cycles, have an equally tight description when mz is at most 3. They must be subgraphs of one of three forms: a star plus one separate edge and isolated vertices; three separate edges and isolated vertices; or a star with one edge subdivided, again with isolated vertices. The statement allows the set of isolated vertices to be empty.
Short cycles leave little room
The restrictions tighten as the shortest cycle gets longer. In graph theory, that shortest-cycle length is the girth. No graph with girth at least 6 can have mz at most 3. At girth 5, the graph must be a 5-cycle together with a possibly empty set of isolated vertices.
For girth 4, every graph with mz at most 3 is isomorphic to one of the structures shown in Figure 3. Because those structures are not fully enumerated in the supplied extraction, their exact shapes are not identified here.
The girth-3 result is narrower. Under its stated configuration assumptions, at least three lilac edges are required. If exactly three occur, they are (V12, V13), (V12, V23) and (V13, V23). The theorem also says lilac edges may be optional, pink vertices are complete subgraphs, and the orange vertex is either complete or independent. It is a partial configuration description, not a complete account of every girth-3 graph in the class.
Enumeration turns the theory into a search
To enumerate allowable graphs, the computational procedure starts with a family of 25 forbidden graphs. It builds possible edge configurations, checks them for forbidden members, and runs the combinations in parallel. A configuration with no forbidden graph is treated as allowable.
That search produced around 2,000 allowable graphs. After graphs with twin vertices were filtered out, 449 non-isomorphic allowable graphs remained. In practical terms, the final count represents 449 distinct graph shapes up to relabeling of their vertices.
The paper also examines vertex blow-ups, a construction in which a vertex is replaced by a complete graph or an independent set. In the cases analyzed, Vt is the only vertex that sometimes permits those replacements. Appendix A.1 reports a file containing the 449 graphs and their forbidden graphs per vertex, with graph encodings described for SageMath use.
Taken together, the findings provide a finite boundary for the search and exact results for forests and several girth classes, while leaving the triangle-containing case only partly described. The complete forbidden set at mz at most 3 is tied to Figure 2, and the girth-4 structures to Figure 3; the supplied extraction does not textually identify all of those graphs. The work therefore offers a map of the allowed and forbidden territory, but not a fully textual catalogue of every shape.
The document is an arXiv version 1 preprint in math.CO dated 28 August 2026. Its results concern abstract graph classes and computational enumeration, not empirical or population-level evidence.
Paper data and sources
Original title: The forbidden structure for zero forcing number
Authors: Carlos A. Alfaro, Michael D. Barrus, Sergio Gerardo Gómez-Galicia et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-28
DOI: Not available
Original paper · Full text