Bondage number

Examples and specific values

For several standard families of graphs, exact values of the bondage number are known:^[1]

For the complete graph $K n$ with $n \geq 2$ vertices, $b (K n) = ⌈ n /2⌉$ .

For the cycle graph $C n$ with $n \geq 3$ vertices, $b (C n) = 3$ if $n \equiv 1 (mod 3)$ , and $b (C n) = 2$ otherwise.

For the path graph $P n$ with $n \geq 2$ vertices, $b (P n) = 2$ .

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 $G$ of order $p$ with maximum degree $Δ(G)$ and minimum degree $δ(G)$ , the following inequalities hold:^[1]^[2]

$b (G) \leq min {u, v} \in E (G) (deg(u) + deg(v) - 1)$

$b (G) \leq Δ(G) + δ(G) - 1$

$b (G) \leq p - 1$

$b (G) \leq (γ(G) - 1)Δ(G) + 1$ if $γ(G) \geq 2$

$b (G) \leq p - γ(G) + 1$ , where $γ(G)$ is the domination number

$b (G) \leq λ(G) + Δ(G) - 1$ , where $λ(G)$ 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.^[3] 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 $b (G) \leq 1$ .^[4] 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.^[3]

Conjectures

Unsolved problem in mathematics

For the bondage number

b (G)

and maximum degree

Δ(G)

of a graph

G

, is

b (G) \leq (3/2)Δ(G)

for all graphs?

Planar graphs

For planar graphs, Dunbar et al. conjectured in 1998:

G

is a planar graph, then

b (G) \leq Δ(G) + 1

This conjecture has been verified for planar graphs with $Δ(G) \geq 7$ and for various other special cases, but remains open in general. It is known that $b (G) \leq min(8, Δ(G) + 2)$ for any connected planar graph $G$ .^[3]

Variations

Several variations of the bondage number have been studied based on different types of domination. The total bondage number considers total dominating sets (where every vertex in the dominating set must also be adjacent to another vertex in the dominating set).^[4] The Roman bondage number is based on Roman domination, where vertices are assigned values 0, 1, or 2 subject to certain constraints.^[6] Further generalizations include the double Roman bondage number,^[7] the independent Roman bondage number,^[8] and the quasi-total Roman bondage number.^[9] Other variations include the k-power bondage number,^[10] the cobondage number,^[11] and the lower bondage number.^[12]

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.^[1]