Teschner's Bondage Number Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G=(V,E)$ be a finite simple undirected graph with at least one edge. A set $D\subseteq V$ dominates $G$ when every vertex outside $D$ is adjacent to a vertex in $D$. The domination number $\gamma(G)$ is the minimum size of a dominating set. For $F\subseteq E$, the graph $G-F$ has the same vertices and the remaining edges. The bondage number is \[ b(G)=\min\{|F|:F\subseteq E,\ \gamma(G-F)>\gamma(G)\}. \] This minimum exists because deleting every edge gives domination number $|V|$, while a graph with an edge has smaller domination number. Write $\Delta(G)$ for maximum vertex degree.

Statement recorded in the supplied source.

Does every finite simple graph with at least one edge satisfy \[ b(G)\le\frac32\Delta(G), \] equivalently $b(G)\le\lfloor3\Delta(G)/2\rfloor$? The floor is the greatest integer not exceeding its argument. No connectedness, planarity or surface-embedding assumption is imposed. Edgeless graphs, on which no edge removal can increase domination number, are outside the domain of the bondage-number minimum. [S2]

Short English statement

Can the domination number of every graph with an edge be increased by removing at most three halves of its maximum degree in edges?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1442 (GRAPH-055). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Andrei Gagarin and Vadim Zverovich, The Bondage Number of Graphs on Topological Surfaces and Teschner’s Conjecture, arXiv:1209.1362v1 (2012), Section 1, definitions and Conjecture 1, pages 1--2. https://arxiv.org/pdf/1209.1362v1.