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-2h 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 ^z3+2 ^z2+(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χ-12⌉ for χ≤0, and a further improvement for graphs with large girth.