A counterexample to the zero forcing versus independence conjecture for cubic and subcubic graphs
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.23664
curl -X POST /api/v1/records/arxiv/2607.23664/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.23664/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'