A Counterexample to Teschner's Bondage-Number Conjecture

@misc{yavari2026counterexample,
  title = {{A Counterexample to Teschner's Bondage-Number Conjecture}},
  author = {Yousof Yavari},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.04257},
  eprint = {2609.04257},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.04257},
}

TY  - UNPB
TI  - A Counterexample to Teschner's Bondage-Number Conjecture
AU  - Yousof Yavari
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.04257
UR  - https://arxiv.org/abs/2609.04257
AB  - For a finite simple graph G with at least one edge, the bondage number b(G) is the least number of edges whose deletion increases the domination number γ(G). Teschner conjectured that b(G)≤ 3/2Δ(G) for every graph G. We disprove this conjecture by giving a connected cubic bipartite graph on eighteen vertices with γ(G)=6 and b(G)=5. The domination number is established by a complete counting argument across the bipartition. An explicit five-edge deletion raises the domination number from six to seven. For the matching lower bound, we give an exact finite certificate: the graph has 297 minimum dominating sets, and deleting any one of its binom274=17,550 four-edge subsets leaves at least one of those sets dominating. The enumeration is deterministic, uses only exact integer and set operations, and is reproduced by the complete standard-library verifier included in the appendix.
ER  -