Source-linked AI summary
A Counterexample to Teschner's Bondage-Number Conjecture
Yousof Yavari
TL;DR
The paper addresses whether Teschner’s proposed bondage-number bound holds for every finite simple graph with an edge. It constructs a connected cubic bipartite counterexample and establishes γ(G)=6 and b(G)=5, disproving the conjecture.
Problem
The paper addresses whether Teschner’s conjectured bondage-number bound holds for every finite simple graph with at least one edge.
Source: §1 · p. 1Method
The authors construct a connected cubic bipartite graph, prove its domination number and bondage upper bound by hand, and certify the lower bound by exact finite computation.
Source: §1 · pp. 1–2Results
γ(G)=6 and b(G)=5 for the connected cubic bipartite graph, so Teschner’s conjecture is false.
Source: §1 · p. 2Takeaways & Limitations
The example disproves Teschner’s conjecture within the class of connected cubic bipartite graphs.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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 \tfrac32\Delta(G)$ for every graph $G$. We disprove this conjecture by giving a connected cubic bipartite graph on eighteen vertices with \[ \gamma(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 $\binom{27}{4}=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.
1. Introduction
The paper presents a connected cubic bipartite counterexample to Teschner’s conjecture, with domination number 6 and bondage number 5. It establishes the domination number and an upper bound handcheckably, and the matching lower bound by exact finite computation.
1. Introduction
- Earlier work established the conjecture for broad classes of graphs but did not settle it in full.Source: §1 · p. 1
- The paper frames Teschner’s conjecture as a universal bondage-number bound for finite simple graphs with at least one edge.Source: §1 · p. 1
- γ(G)=6 and b(G)=5 for a connected cubic bipartite graph, making it a counterexample to Teschner’s conjecture.Source: §1 · p. 2
- The proof of γ(G)=6 and b(G)≤5 is handcheckable, while the lower bound b(G)≥5 comes from exact finite computation with a complete verifier.Source: §1 · p. 2
2. Preliminaries
The preliminaries set out neighborhood and edge-deletion notation, basic facts about domination, and a criterion for checking whether a fixed dominating set survives edge deletion.
2. Preliminaries
- N_G(v) and N_G[v] denote the open and closed neighborhoods, and D dominates G exactly when N_G[D]=V(G).Source: §2 · p. 2
- The notation G−F denotes deleting edge set F, and domination numbers are monotone under edge deletion and add over graph components.Source: §2 · p. 2
- A fixed dominating set D remains dominating after deleting F exactly when no outside vertex has all its D-neighbor edges contained in F.Source: §2 · p. 3
3. The graph and its domination number
The section establishes the graph’s connected, cubic, bipartite structure and uses a counting argument across its bipartition to rule out dominating five-sets. It also gives adjacency witnesses showing that D0 dominates the graph.
3. The graph and its domination number
- The graph is connected, cubic, and bipartite; each vertex in X has three neighbors, and every vertex in Y occurs in three listed neighborhoods.Connectivity is established by showing that the distance layers from vertex 0 cover the graph.Source: §3 · p. 3
- For a hypothetical dominating five-set, bipartition counts force a=|D ∩ X| to be 2 or 3.The bounds follow from 9 − a ≤ 3(5 − a) and 4 + a ≤ 3a.Source: §3 · p. 4
- No five-set dominates G: the exhaustive pair list in Table 2 yields, in every row, an undominated vertex.The proof uses this to rule out dominating sets of cardinality five.Source: §3 · p. 4, Table 2 · p. 5
- Adjacency witnesses are given for the vertices outside D0, establishing that D0 dominates G.The listed witnesses identify a selected adjacent vertex for each outside vertex.Source: §3 · p. 5
4. The bondage number
A five-edge deletion raises the domination number from six to seven, while the exact four-edge certificate shows that no four-edge deletion suffices. Together these results establish the bondage number as five and disprove the conjecture.
4. The bondage number
- γ(G −F5) = 7 > 6 = γ(G) after the specified five-edge deletion.The deletion isolates two adjacent vertices, and the remaining graph H has domination number five.Source: §4 · pp. 5–6
- 297 minimum dominating sets and the exhaustive four-edge test certify that every four-edge deletion leaves at least one of them dominating.The verifier tests the bundle condition for each minimum set and each vertex outside it; consequently γ(G −F) = 6 for every four-edge set F.Source: §4 · p. 6
- Deleting at most four edges never increases the domination number, so b(G) = 5.The lower bound combines with the explicit five-edge deletion to establish the exact value.Source: §4 · pp. 5, 7
- The resulting value disproves Conjecture 1.1.Source: §4 · p. 7
Appendix A. Exact verifier
The appendix supplies the complete standard-library verifier used for the exact certificate. It enumerates six-vertex dominating sets and checks the four-edge deletions against them.
Appendix A. Exact verifier
- The complete Python 3 verifier reproduces the certificate's enumerated values and terminates without error.It represents vertices and edges by the explicit finite sets in the proof.Source: Appendix A · p. 7
- The program enumerates six-vertex subsets and retains those that dominate the graph, checking that the resulting collection has size 297.Source: Appendix A · pp. 7–8
- For each four-edge subset, the verifier tests whether any minimum set survives, and checks that the minimum survivor count is one.It also checks that all 17,550 four-edge subsets were examined.Source: Appendix A · p. 8
Generative-AI disclosure
The counterexample was generated with GPT-5.6 Sol Max after Yousof Yavari prompted the model, then Yavari revised and clarified the proof. Yavari is the sole author and accepts responsibility for all manuscript content and results.
Generative-AI disclosure
- Yousof Yavari is the sole author and takes full responsibility for every definition, calculation, inference, computational result, and conclusion.Source: Generative-AI disclosure · p. 9
- GPT-5.6 Sol Max generated the counterexample after Yousof Yavari prompted the model to solve the manuscript’s question.Source: Generative-AI disclosure · p. 9
- Yousof Yavari subsequently revised and edited the proof, added details, and clarified its exposition.Source: Generative-AI disclosure · p. 9