Bondage number

The domination number of the graph on the left can be strictly increased by 1 when removing a minimum of 2 edges, shown on the right. The highlighted vertices show a minimum dominating set for each graph.

In the mathematical field of graph theory, the bondage number of a nonempty graph G is the cardinality of the smallest set of edges whose removal results in a domination number strictly greater than the domination number γ(G) of G. The bondage number is denoted b(G).

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 K_n with n ≥ 2 vertices, b(K_n) = ⌈n/2⌉.

• For the cycle graph C_n with n ≥ 3 vertices, b(C_n) = 3 if n ≡ 1 (mod 3), and b(C_n) = 2 otherwise.

• For the path graph P_n with n ≥ 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:

• b(G) ≤ min_{{u,v} ∈ E(G)} (deg(u) + deg(v) − 1)

• b(G) ≤ Δ(G) + δ(G) − 1

• b(G) ≤ p − 1

• b(G) ≤ (γ(G) − 1)Δ(G) + 1 if γ(G) ≥ 2

• b(G) ≤ p − γ(G) + 1, where γ(G) is the domination number

• b(G) ≤ λ(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. 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) ≤ 1. 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

Unsolved problem in mathematics

For the bondage number b(G) and maximum degree Δ(G) of a graph G, is b(G) ≤ (3/2)Δ(G) for all graphs?

More unsolved problems in mathematics

A conjecture by Fink et al. from 1990 stated that for any nonempty graph G,

b(G) ≤ Δ(G) + 1.

However, this was disproved by Teschner in 1993, who showed that the Cartesian product K₃ □ K₃ has b(K₃ □ K₃) = Δ(K₃ □ K₃) + 2. More generally, Hartnell-Rall and Teschner independently showed that b(K_n □ K_n) = (3/2)Δ(K_n □ K_n) for n ≥ 3. They also provided a 4-regular bipartite graph with bondage number 6 as another counterexample.

Teschner then proposed the following weaker conjecture:

For any graph G, b(G) ≤ (3/2)Δ(G).

This conjecture remains open.

Planar graphs

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

If G is a planar graph, then b(G) ≤ Δ(G) + 1.

This conjecture has been verified for planar graphs with Δ(G) ≥ 7 and for various other special cases, but remains open in general. It is known that b(G) ≤ min(8, Δ(G) + 2) for any connected planar graph G.

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). 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.

Related problems

The reinforcement number r(G) is the minimum number of edges that must be added to G to decrease its domination number. Like the bondage number, determining the reinforcement number is NP-hard even for bipartite graphs.