arxiv: 2605.10836 · v1 · submitted 2026-05-11 · 💻 cs.DM

Recognition: 2 theorem links

· Lean Theorem

The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction

Samuel German

Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:20 UTC · model grok-4.3

classification 💻 cs.DM

keywords zero forcingpath-extremal conjecturedistance-hereditary graphssplit decompositionzero forcing polynomialfortscographsgraph polynomials

0 comments

The pith

The path on n vertices maximizes the number of zero forcing sets of every size among all distance-hereditary n-vertex graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves the path-extremal conjecture for zero forcing on distance-hereditary graphs, a class that includes all trees and all cographs. The authors use counting mechanisms for non-forcing sets based on twin pairs and leaf recurrences, along with the structure of canonical split decompositions, to show that the zero forcing polynomial is coefficientwise dominated by that of the path. They further show that the property lifts from split-prime graphs to graphs whose decomposition has a unique prime bag matching such a graph. This makes the conjecture a finite verification problem for classes with bounded prime bag size.

Core claim

We prove the path-extremal conjecture for distance-hereditary graphs: the zero forcing polynomial of any such graph is coefficientwise dominated by that of the path on the same number of vertices. We then show that if a split-prime graph H and all its induced subgraphs are path-extremal, then every connected graph whose canonical split decomposition has a unique prime bag isomorphic to H is also path-extremal. Consequently, for each fixed m, the conjecture holds for all connected graphs with a unique prime bag of size at most m, assuming it holds for all split-prime graphs on at most m vertices and their induced subgraphs.

What carries the argument

The combination of fort obstructions from twin pairs, leaf recurrence for counting non-forcing sets, and the accessibility description of graph-labelled trees in the canonical split decomposition.

If this is right

The conjecture holds for all cographs.
If the conjecture is true for all split-prime graphs up to a fixed size m and their subgraphs, then it holds for all connected graphs with a unique prime bag of size at most m.
The path-extremal property propagates through the split decomposition when there is a unique prime bag.
The proof technique identifies a structural boundary for further verification of the conjecture.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Computational checks on small split-prime graphs could resolve the conjecture for all graphs with bounded decomposition complexity.
The reduction suggests that distance-hereditary graphs represent a maximal class where the conjecture can be proved without additional assumptions on primes.
Extending to multiple prime bags might require new counting arguments that account for interactions between bags.

Load-bearing premise

That the fort obstructions from twin pairs and the leaf recurrence, when combined with the accessibility description of the graph-labelled trees, are sufficient to establish the coefficientwise domination by the path polynomial.

What would settle it

Discovery of a distance-hereditary graph on n vertices for which, for some k, the number of size-k zero forcing sets exceeds the corresponding number for the n-vertex path.

read the original abstract

For an $n$-vertex graph $G$, let $z(G;k)$ denote the number of zero forcing sets of size $k$. A conjecture of Boyer et al. asserts that the path $P_n$ maximizes these numbers coefficientwise among all $n$-vertex graphs; equivalently, the zero forcing polynomial of every $n$-vertex graph should be coefficientwise dominated by that of $P_n$. We prove this path-extremal conjecture for distance-hereditary graphs. This extends the previously known tree case to a much larger class that includes, in particular, all trees and all cographs. We then use canonical split decomposition to push the argument one step beyond the distance-hereditary setting. Specifically, we show that if a split-prime graph $H$ and all of its induced subgraphs are path-extremal, then every connected graph whose canonical split decomposition has a unique prime bag whose label graph is isomorphic to $H$ is also path-extremal. As a corollary, for each fixed $m$, if every induced subgraph of every split-prime graph on at most $m$ vertices is path-extremal, then so is every connected graph whose canonical split decomposition has a unique prime bag of size at most $m$. Thus, on these classes, the conjecture reduces to a finite verification problem on bounded-order prime cores. Our proofs combine two counting mechanisms for non-forcing sets -- fort obstructions arising from twin pairs and a leaf recurrence -- with the accessibility description of graph-labelled trees in the canonical split decomposition. This yields a new positive instance of the path-extremal conjecture and identifies a natural structural frontier for further progress.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves the path-extremal zero forcing conjecture on distance-hereditary graphs and reduces further cases to finite checks on split-prime graphs.

read the letter

This paper proves the path-extremal conjecture for zero forcing on distance-hereditary graphs, extending the tree case, and it provides a split-decomposition reduction that narrows the conjecture to checks on split-prime graphs. The new part is the proof for distance-hereditary graphs, which properly contains trees and includes all cographs. They achieve this by combining two counting mechanisms for non-forcing sets: fort obstructions that come from twin pairs and a leaf recurrence. These are then linked to the accessibility description of graph-labelled trees that arises in the canonical split decomposition. The result is that the zero forcing polynomial of any such graph is coefficientwise dominated by the one for the path on the same number of vertices. The reduction step is also new: if a split-prime graph H and all its induced subgraphs satisfy the path-extremal property, then any connected graph whose canonical split decomposition has a unique prime bag isomorphic to H will also satisfy it. A corollary is that for any fixed m, the conjecture holds for all connected graphs whose unique prime bag has size at most m, provided it holds for all induced subgraphs of all split-prime graphs on at most m vertices. This makes the remaining work a finite verification task on bounded-order prime cores. The paper does this well. The arguments rely on standard structural properties of the graph classes involved and do not appear to introduce circularity or uncovered cases. The mechanisms seem to partition the non-forcing sets completely for distance-hereditary graphs, supporting the domination claim. The reduction is a clean structural result that identifies a natural frontier for further progress without overreaching. There are no major soft spots. The only minor limitation is that while the reduction reduces the problem to finite checks, performing those checks for larger m would still require significant computational or case-analysis work, but the paper presents this accurately as a reduction rather than a full solution. The citation pattern looks appropriate, building on the prior tree literature without unnecessary self-reference. This paper is for researchers in extremal graph theory and zero forcing who are interested in structural approaches to such conjectures. A reader familiar with distance-hereditary graphs or split decompositions will find the techniques useful and the result relevant. It deserves a serious referee because it delivers a genuine new positive instance of the conjecture on a larger class and supplies a concrete way to make further progress. I would recommend sending this to peer review.

Referee Report

0 major / 3 minor

Summary. The paper proves the path-extremal conjecture for zero forcing: for every n-vertex distance-hereditary graph G, the zero-forcing polynomial of G is coefficientwise dominated by that of the path P_n. The proof combines fort obstructions arising from twin pairs with a leaf recurrence, using the accessibility description of graph-labelled trees. It further establishes a reduction: if a split-prime graph H and all its induced subgraphs are path-extremal, then every connected graph whose canonical split decomposition has a unique prime bag isomorphic to H is path-extremal. As a corollary, the conjecture reduces to finite verification on bounded-order split-prime cores for certain classes.

Significance. If the central claims hold, the result extends the known tree case to the substantially larger class of distance-hereditary graphs (including all cographs) and supplies a structural reduction via canonical split decomposition that converts the conjecture into a finite check for graphs with bounded prime-bag size. The combination of twin-pair obstructions, leaf recurrence, and graph-labelled-tree accessibility appears to partition non-forcing sets completely without free parameters or circularity, providing a clean positive instance and a natural frontier for further work.

minor comments (3)

[§2] §2 (Preliminaries): the definition of a fort and the precise statement of the leaf recurrence are introduced after their first use in the counting argument; moving the definitions earlier would improve readability.
[§4] §4 (Reduction theorem): the accessibility description of graph-labelled trees is invoked without a self-contained recap of the key lemmas from the split-decomposition literature; a short paragraph summarizing the needed properties would make the argument easier to follow.
Throughout: several coefficientwise inequalities are stated without an explicit reference to the corresponding lemma or proposition number in the same section, requiring the reader to backtrack.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, the accurate summary of our results on the path-extremal conjecture for distance-hereditary graphs, and the recommendation of minor revision. The significance assessment correctly identifies the extension from trees to distance-hereditary graphs and the utility of the split-decomposition reduction. Since the report contains no specific major comments or requested changes, we have no revisions to incorporate at this time.

Circularity Check

0 steps flagged

No circularity; derivation self-contained via structural counting

full rationale

The paper establishes the path-extremal conjecture for distance-hereditary graphs by combining fort obstructions from twin pairs, leaf recurrence for non-forcing sets, and accessibility in graph-labelled trees from canonical split decomposition. These are standard structural tools applied to the class, with the split-prime reduction reducing the problem to finite verification on bounded cores. No step equates a derived quantity to a fitted input by construction, renames a known result, or relies on a load-bearing self-citation whose validity is internal to the paper. The tree case is cited as prior (Boyer et al.), and the argument partitions non-forcing sets independently for the target class.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on established graph-theoretic structures rather than introducing new fitted parameters or entities.

axioms (2)

domain assumption Distance-hereditary graphs admit the described twin-pair and leaf-recurrence counting for non-forcing sets.
Invoked to establish coefficientwise domination by the path polynomial.
domain assumption Canonical split decomposition yields graph-labelled trees whose accessibility description interacts cleanly with the zero-forcing counting.
Used to push the argument beyond distance-hereditary graphs.

pith-pipeline@v0.9.0 · 5609 in / 1358 out tokens · 45227 ms · 2026-05-12T04:20:04.391111+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our proofs combine two counting mechanisms for non-forcing sets—fort obstructions arising from twin pairs and a leaf recurrence—with the accessibility description of graph-labelled trees in the canonical split decomposition.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 7. If u and v form a twin pair in G, then {u, v} is a fort.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Linear Algebra and its Applications428(7), 1628–1648 (2008)

AIM Minimum Rank – Special Graphs Work Group: Zero forcing sets and the minimum rank of graphs. Linear Algebra and its Applications428(7), 1628–1648 (2008). https://doi.org/10.1016/j.laa.2007.10.009

work page doi:10.1016/j.laa.2007.10.009 2008
[2]

The Electronic Journal of Combinatorics25(4), P4.47 (2018)

Bahrani, M., Lumbroso, J.: Enumerations, forbidden subgraph characterizations, and the split-decomposition. The Electronic Journal of Combinatorics25(4), P4.47 (2018). https://doi.org/10.37236/6431

work page doi:10.37236/6431 2018
[3]

Journal of Combi- natorial Theory, Series B41(2), 182–208 (1986)

Bandelt, H.J., Mulder, H.M.: Distance-hereditary graphs. Journal of Combi- natorial Theory, Series B41(2), 182–208 (1986). https://doi.org/10.1016/0095- 8956(86)90043-2

work page doi:10.1016/0095- 1986
[4]

Linear Algebra and its Applications433(2), 401–411 (2010)

Barioli, F., Barrett, W., Fallat, S.M., Hall, H.T., Hogben, L., Shader, B.L., van den Driessche, P., van der Holst, H.: Zero forcing parameters and mini- mum rank problems. Linear Algebra and its Applications433(2), 401–411 (2010). https://doi.org/10.1016/j.laa.2010.03.008

work page doi:10.1016/j.laa.2010.03.008 2010
[5]

Discrete Applied Math- ematics258, 35–48 (2019)

Boyer, K., Brimkov, B., English, S., Ferrero, D., Keller, A., Kirsch, R., Phillips, M., Reinhart, C.: The zero forcing polynomial of a graph. Discrete Applied Math- ematics258, 35–48 (2019). https://doi.org/10.1016/j.dam.2018.11.033

work page doi:10.1016/j.dam.2018.11.033 2019
[6]

Natural Computing14, 485–490 (2015)

Burgarth, D., Giovannetti, V., Hogben, L., Severini, S., Young, M.: Logic circuits from zero forcing. Natural Computing14, 485–490 (2015). https://doi.org/10.1007/s11047-014-9438-5

work page doi:10.1007/s11047-014-9438-5 2015
[7]

Discrete Mathematics347(5), 113944 (2024)

Curtis, B., Gan, L., Haddock, J., Lawrence, R., Spiro, S.: Zero forcing with random sets. Discrete Mathematics347(5), 113944 (2024)

work page 2024
[8]

European Journal of Combinatorics91, 103207 (2021)

English, S., MacRury, C., Prałat, P.: Probabilistic zero forcing on ran- dom graphs. European Journal of Combinatorics91, 103207 (2021). https://doi.org/10.1016/j.ejc.2020.103207

work page doi:10.1016/j.ejc.2020.103207 2021
[9]

The minimum rank of symmetric matrices described by a graph: A survey

Fallat, S.M., Hogben, L.: The minimum rank of symmetric matrices described by a graph: A survey. Linear Algebra and its Applications426(2–3), 558–582 (2007). https://doi.org/10.1016/j.laa.2007.05.036

work page doi:10.1016/j.laa.2007.05.036 2007
[10]

Discrete Applied Mathematics160(6), 708–733 (2012)

Gioan, E., Paul, C.: Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decompos- able graphs. Discrete Applied Mathematics160(6), 708–733 (2012). https://doi.org/10.1016/j.dam.2011.05.007

work page doi:10.1016/j.dam.2011.05.007 2012
[11]

Discrete Applied Mathematics160(13–14), 1994–2005 (2012)

Hogben, L., Huynh, M., Kingsley, N., Meyer, S., Walker, S., Young, M.: Propaga- tion time for zero forcing on a graph. Discrete Applied Mathematics160(13–14), 1994–2005 (2012). https://doi.org/10.1016/j.dam.2012.04.003

work page doi:10.1016/j.dam.2012.04.003 1994
[12]

Bulletin of the Institute of Combinatorics and its Applications67, 9–16 (2013)

Kang, C.X., Yi, E.: Probabilistic zero forcing in graphs. Bulletin of the Institute of Combinatorics and its Applications67, 9–16 (2013)

work page 2013
[13]

Linear Algebra and its Applications576, 124–141 (2019)

Kenter, F.H.J., Lin, J.C.H.: On the error of a priori sampling: Zero forcing sets and propagation time. Linear Algebra and its Applications576, 124–141 (2019). https://doi.org/10.1016/j.laa.2018.03.031

work page doi:10.1016/j.laa.2018.03.031 2019
[14]

Discrete Mathematics348(8), 114516 (2025)

Menon, K., Singh, A.: Exploring the influence of graph operations on zero forcing sets. Discrete Mathematics348(8), 114516 (2025). https://doi.org/10.1016/j.disc.2025.114516

work page doi:10.1016/j.disc.2025.114516 2025
[15]

Linear Algebra and its Applications484, 199–218 (2015)

Tréfois, M., Delvenne, J.C.: Zero forcing number, constrained matchings and strong structural controllability. Linear Algebra and its Applications484, 199–218 (2015). https://doi.org/10.1016/j.laa.2015.06.025 A Split-Decomposition Approach to the Path-Extremal Conjecture 13 Appendix Proof of Lemma 11 Lemma 14.LetHbe a split-prime graph, letG∈ D(H), and fi...

work page doi:10.1016/j.laa.2015.06.025 2015