Teschner's conjecture on the upper bondage number of critical graphs

Let $\mathcal{P} \subseteq \mathcal{G}$ be additive and hereditary. A graph $G$ is vertex- $\gamma_{\mathcal{P}}$ -critical if its vertex domination number with respect to $\mathcal{P}$ has the criticality property used in the paper, and let $b_{\mathcal{P}}^+(G)$ denote its upper bondage number and $\Delta(G)$ its maximum degree. Teschner's conjecture. For any vertex- $\gamma_{\mathcal{P}}$ -critical graph $G$ ,

b_{\mathcal{P}}^+(G) \leq 1.5\Delta(G).

The conjecture is presented as the main outstanding conjecture on the ordinary bondage number when $\mathcal{P}=\mathcal{G}$ ; its general status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Vladimir Samodivkin, “Changing of the domination number of a graph: edge multisubdivision and edge removal”, arXiv:1502.06245 (2015).

Additional references

3 papers in this index state this conjecture (2010–2015). The statement above is taken from the most recent of them; the others are arXiv:1204.4010, arXiv:1012.4117.

1 week ago

Progress summary

Refreshed 3 days ago

Open

The conjecture remains open: no verified proof or counterexample was found for either the general statement or its ordinary graph version.

Teschner proposed the ordinary inequality in 1995; the property-relative version asks whether $b_{\mathcal{P}}^+(G) \leq 1.5\Delta(G)$ holds for every vertex- $\gamma_{\mathcal{P}}$ -critical graph. The supplied sources contain no proof or refutation of this generalization.

Known results

Teschner (1993) disproved the earlier bound $b(G) \leq \Delta(G)+1$ using $K_3 \square K_3$ .
Hartnell–Rall and Teschner independently obtained $b(K_n \square K_n)=1.5\Delta(K_n \square K_n)$ for $n \geq 3$ .
Kang and Yuan (2000) proved the planar bound $b(G) \leq \min\{\Delta(G)+2,8\}$ .
Samodivkin (2013) extended ordinary domination and bondage results to nondegenerate graph properties and posed related conjectures.

Current status (as of August 2026): The ordinary conjecture and the general $\mathcal{P}$ -version remain unproved and unrefuted in the supplied record, despite established special-case bounds.

Sources

No solutions have been posted yet.