TOPICS
Search

Planar Bondage Conjecture

The planar bondage conjecture asserts that every finite connected simple graph G that is planar and has at least one graph edge satisfies

b(G)<=Delta(G)+1,

where b(G) is the bondage number and Delta(G) is the maximum vertex degree. The conjecture was proposed by Dunbar et al. (1998).

Srivastava (2026) disproved the conjecture using the truncated octahedral graph T, which has 24 graph vertices, 36 graph edges, domination number 8, and bondage number 5. The truncated octahedral graph is cubic and planar, so Delta(T)=3 and b(T)=5>4=Delta(T)+1. The proof exhaustively checks that every deletion of four graph edges preserves domination number 8 and exhibits five graph edges whose deletion raises it to 9. Srivastava (2026) reports using OpenAI Codex for search-code development and independent-check design.

See also

Bondage Number, Domination Number, Planar Graph, Truncated Octahedral Graph

Explore with Wolfram|Alpha

References

Dunbar, J. E.; Haynes, T. W.; Teschner, U.; and Volkmann, L. "Bondage, Insensitivity, and Reinforcement." In Domination in Graphs--Advanced Topics (Ed. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater). New York: Marcel Dekker, pp. 471-489, 1998.Srivastava, P. R. "The Truncated Octahedral Graph Has Bondage Number Five." 2 Sep 2026. https://arxiv.org/abs/2609.02477.

Cite this as:

Weisstein, Eric W. "Planar Bondage Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PlanarBondageConjecture.html

Subject classifications