For every nontrivial planar graph G, the bondage number satisfies b(G)≤ Delta(G)+1, where b(G)=min| F|:F⊆ E(G), gamma(G-F)>gamma(G) and gamma(G) is the domination number of G.

Dunbar–Haynes–Teschner–Volkmann planar bondage conjecture

The 1998 Dunbar–Haynes–Teschner–Volkmann conjecture proposed that every planar graph satisfies the universal bound $b(G) \le \Delta(G)+1$ .

Known results

The bound is known for planar graphs with $\Delta(G) \ge 7$ .
Every connected planar graph satisfies $b(G) \le \min(8,\Delta(G)+2)$ .
For chordal graphs, $b(G) \le \omega(G)$ ; hence non-clique planar chordal graphs satisfy $b(G) \le 4$ .

September 2026 counterexample

The preprint The Truncated Octahedral Graph Has Bondage Number Five exhibits a cubic planar graph $T$ with $b(T)=5$ , contradicting the proposed bound $b(T) \le \Delta(T)+1=4$ . Exhaustive computations verify the domination number, bondage number, and relevant four-edge deletions, but the result is unrefereed.

Current status (as of September 2026): The conjecture is claimed refuted by a cubic planar counterexample, but the computational verification has not been independently confirmed.

Dunbar–Haynes–Teschner–Volkmann planar bondage conjecture

Primary source

Additional references

Progress summary

Solutions 0