A graph whose zero-forcing polynomial is not unimodal

The zero-forcing polynomial of a graph counts its zero-forcing sets by cardinality. We give a graph on 73 vertices with $2096$, $1592$ and $1600$ zero-forcing sets of sizes 69, 70 and 71, respectively. This answers in the negative the question of Boyer and coauthors whether the zero-forcing polynomial of every graph is unimodal. The graph joins two disjoint complete graphs, of orders 32 and 33, to four disjoint edges. The proof is a short count: vertices in each clique have the same neighbors outside it, and a zero-forcing set can leave at most one vertex of each clique uncolored. Wang's Lemma 3.5 and Corollary 3.6 establish this principle more generally and count the choices within each group by its size. We apply that principle to this explicit graph and classify the remaining possibilities by the numbers of uncolored vertices on each side of the join. Two independent exact programs confirm the resulting polynomial. This work has not yet been reviewed by experts. The proofs, the certificate checkers, the figure and the text were produced by AI models (from OpenAI and Anthropic), working under the author's direction. Computer-assisted; not yet reviewed by experts. Produced by AI models under the author's direction.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-01
DOI
https://doi.org/10.5281/zenodo.23875152
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A graph whose zero-forcing polynomial is not unimodal

P. Graham
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

A graph whose zero-forcing polynomial is not unimodal

P. Graham
preprint en

Abstract

The zero-forcing polynomial of a graph counts its zero-forcing sets by cardinality. We give a graph on 73 vertices with $2096$, $1592$ and $1600$ zero-forcing sets of sizes 69, 70 and 71, respectively. This answers in the negative the question of Boyer and coauthors whether the zero-forcing polynomial of every graph is unimodal. The graph joins two disjoint complete graphs, of orders 32 and 33, to four disjoint edges. The proof is a short count: vertices in each clique have the same neighbors outside it, and a zero-forcing set can leave at most one vertex of each clique uncolored. Wang's Lemma 3.5 and Corollary 3.6 establish this principle more generally and count the choices within each group by its size. We apply that principle to this explicit graph and classify the remaining possibilities by the numbers of uncolored vertices on each side of the join. Two independent exact programs confirm the resulting polynomial. This work has not yet been reviewed by experts. The proofs, the certificate checkers, the figure and the text were produced by AI models (from OpenAI and Anthropic), working under the author's direction. Computer-assisted; not yet reviewed by experts. Produced by AI models under the author's direction.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon