A Counterexample to Teschner's Bondage-Number Conjecture

Abstract

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 $\gamma (G)$. Teschner conjectured that $b(G)\le \frac{3}{2}\Delta (G)$ for every graph $G$. We disprove this conjecture by giving a connected cubic bipartite graph on eighteen vertices with \[ γ(G)=6 \qquad\text{and}\qquad 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 $\left(\genfrac{}{}{0ex}{}{27}{4}\right)=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.

9 pages, no figures; complete Python 3 verifier included in the appendix