2013/05/24 by Samodivkin, Vladimir
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1305.5692
The bondage number b(G) of a graph G is the smallest number of edges whose removal from G results in a graph with larger domination number. An orientable surface \mathbbSh of genus h, h ≥ 0, is obtained from the sphere \mathbbS0 by adding h handles. A non-orientable surface ℕq of genus q, q ≥ 1, is obtained from the sphere by adding q crosscaps. The Euler characteristic of a surface is defined by χ(\mathbbSh) = 2 - 2h and χ(\mathbbSq)= 2-q. Let G be a connected graph of order n which is 2-cell embedded on a surface \mathbbM with χ(\mathbbM)= χ. We prove that b(G) ≤ 7+i when \mathbbM = ℕi, i=1,2,3, and b(G) ≤ 12 when \mathbbM ∈ \ℕ4, \mathbbS2\. We give new arguments that improve the known upper bounds on the bondage number at least when -7χ/(δ(G) - 5) < n ≤ -12χ, δ(G) ≥ 6, where δ(G) is the minimum degree of G. We obtain sufficient conditions for the validity of the inequality b(G) ≤ 2s-2, provided G has degree s vertices. In particular, we prove that if δ(G) = δ≥ 6, χ≤ -1 and -14χ< δ- 4 + 2(δ-5)n then b(G) ≤ 2δ-2. We show that if γ(G) = γ\not = 2, where γ(G) is the domination number of G, then n ≥ γ+ (1 + √(9+8γ-8χ))/2; the bound is tight. We also present upper bounds for the bondage number of graphs in terms of the girth, domination number and Euler characteristic. As a corollary we prove that if γ(G) ≥ 4 and χ≤ -1, then b(G) ≤ 11 - 24χ/(9 + √(41 - 8χ)). Several unanswered questions are posed.