An improved upper bound for the bondage number of graphs on surfaces

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. Recently Gagarin and Zverovich showed that, for a graph G with maximum degree Δ ( G ) and embeddable on an orientable surface of genus h and a non-orientable surface of genus k , b ( G ) ≤ min { Δ ( G ) + h + 2 , Δ + k + 1 } . They also gave examples showing that adjustments of their proofs implicitly provide better results for larger values of h and k . In this paper we establish an improved explicit upper bound for b ( G ) , using the Euler characteristic χ instead of the genera h and k , with the relations χ = 2 − 2 h and χ = 2 − k . We show that b ( G ) ≤ Δ ( G ) + ⌊ r ⌋ for the case χ ≤ 0 (i.e. h ≥ 1 or k ≥ 2 ), where r is the largest real root of the cubic equation z 3 + 2 z 2 + ( 6 χ − 7 ) z + 18 χ − 24 = 0 . Our proof is based on the technique developed by Carlson–Develin and Gagarin–Zverovich, and includes some elementary calculus as a new ingredient. We also find an asymptotically equivalent result b ( G ) ≤ Δ ( G ) + ⌈ 12 − 6 χ − 1 / 2 ⌉ for χ ≤ 0 , and a further improvement for graphs with large girth.