A counterexample to the zero forcing versus independence conjecture for cubic and subcubic graphs

Mikko Fischer

Abstract

We exhibit a connected graph on 24 vertices with maximum degree 3, independence number 9 and zero forcing number 11, refuting a 2017 conjecture of TxGraffiti recorded as Conjecture 2 of the survey of Davila, Brimkov and Pepper. The same construction with a different gadget gives a connected cubic graph on 36 vertices with independence number 15 and zero forcing number 17; the conjecture therefore fails also in the cubic form in which the survey's Lean 4 appendix states it. In particular Z <= alpha + 1 is not a universal bound for connected cubic graphs, and the value Z = alpha + 2 is attained.

Disclosure

“50. Key words and phrases. zero forcing number, independence number, cubic graph, TxGraffiti. The counterexamples were found with the assistance of Claude Opus 5 (Anthropic), directed by the author. The author has independently executed the verification script included in the ancillary files and checked its outp”
PDF page 1

Classification: Substantial mathematical content or result generation
Multiplier: 10
Verified: 2026-08-23T19:07:29.759828Z

Structural counts

Pages 3 pdf

Theorems 1 source

Lemmas 0 source

Propositions 0 source

Corollaries 0 source

Definitions 0 source

Displayed equations 3 source

Bibliography entries 4 source

Appendix pages 0 estimated

Count notes

Source counts use the expanded primary TeX file note.tex.
Appendix pages include the first PDF page with an explicit Appendix heading through the final page.