The Truncated Octahedral Graph Has Bondage Number Five

@misc{srivastava2026truncated,
  title = {{The Truncated Octahedral Graph Has Bondage Number Five}},
  author = {Prateek R. Srivastava},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.02477},
  eprint = {2609.02477},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02477},
}

TY  - UNPB
TI  - The Truncated Octahedral Graph Has Bondage Number Five
AU  - Prateek R. Srivastava
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2609.02477
UR  - https://arxiv.org/abs/2609.02477
AB  - For a graph G, its bondage number b(G) is the minimum number of edges whose deletion increases its domination number. Dunbar, Haynes, Teschner, and Volkmann conjectured in 1998 that every nontrivial planar graph satisfies b(G) <= Delta(G) + 1. We show that the truncated octahedral graph T has gamma(T) = 8 and b(T) = 5. Since T is planar and cubic, this gives b(T) = 5 > 4 = Delta(T) + 1 and disproves the conjecture. The finite parts of the verification are exhaustive: the direct verifier checks candidate dominating sets of sizes six, seven, and eight and all 58,905 four-edge sets. The targeted discovery search and an independently written verifier are described, and the complete C++20 verifier is included in the source archive.
ER  -