Bondage number

In the mathematical field of graph theory, the bondage number of a nonempty graph is the cardinality of the smallest set of edges whose removal results in a domination number strictly greater than the domination number of. The bondage number is denoted.
The concept was introduced by Fink et al. in 1990 and measures the vulnerability of a graph's domination structure to edge removal.

Examples and specific values

For several standard families of graphs, exact values of the bondage number are known:

For the complete graph with vertices,.
For the cycle graph with vertices, if, and otherwise.
For the path graph with vertices,.
For nontrivial trees, the bondage number is at most 2. A tree has bondage number 1 if any vertex is adjacent to two or more leaves.

Bounds

Several general bounds on the bondage number have been established. For a connected graph of order with maximum degree and minimum degree, the following inequalities hold:

if
, where is the domination number
, where is the edge connectivity

Computational complexity

Determining the bondage number of a general graph is NP-hard, as shown by Hu and Xu in 2012. This hardness result has been strengthened to show that the bondage problem remains NP-hard even when restricted to bipartite graphs and even when asking whether. This is because if a polynomial time algorithm existed for computing bondage numbers, it could be used to compute domination numbers in polynomial time, which is known to be NP-complete.
However, for special classes of graphs, efficient algorithms exist. In particular, the bondage number of any tree can be determined in O(n) time using a linear algorithm developed by Hartnell et al.

Conjectures

A conjecture by Fink et al. from 1990 stated that for any nonempty graph,
However, this was disproved by Teschner in 1993, who showed that the Cartesian product has. More generally, Hartnell-Rall and Teschner independently showed that for. They also provided a 4-regular bipartite graph with bondage number 6 as another counterexample.
Teschner then proposed the following weaker conjecture:
This conjecture remains open.

Planar graphs

For planar graphs, Dunbar et al. conjectured in 1998:
This conjecture has been verified for planar graphs with and for various other special cases, but remains open in general. It is known that for any connected planar graph.

Variations

Several variations of the bondage number have been studied based on different types of domination. The total bondage number considers total dominating sets. The Roman bondage number is based on Roman domination, where vertices are assigned values 0, 1, or 2 subject to certain constraints. Further generalizations include the double Roman bondage number, the independent Roman bondage number, and the quasi-total Roman bondage number. Other variations include the k-power bondage number, the cobondage number, and the lower bondage number.

Motivation

The bondage number has applications in analyzing the vulnerability of communication networks. In a network modeled as a graph where vertices represent sites and edges represent direct communication links, a minimum dominating set corresponds to an optimal placement of transmitters so that every site either has a transmitter or is directly connected to a site with a transmitter. The bondage number represents the minimum number of communication links that must fail before an additional transmitter is required to maintain communication with all sites.