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

The bondage number b(G)b(G) of a graph GG is the smallest number of edges whose removal from GG results in a graph with larger domination number. Recently Gagarin and Zverovich showed that, for a graph GG with maximum degree Δ(G)Δ(G) and embeddable on an orientable surface of genus hh and a non-orientable surface of genus kk, b(G)≤min{Δ(G)+h+2,Δ+k+1}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 hh and kk. In this paper we establish an improved explicit upper bound for b(G)b(G), using the Euler characteristic χχ instead of the genera hh and kk, with the relations χ=2−2hχ=2−2h and χ=2−kχ=2−k. We show that b(G)≤Δ(G)+⌊r⌋b(G)≤Δ(G)+⌊r⌋ for the case χ≤0χ≤0 (i.e. h≥1h≥1 or k≥2k≥2), where rr is the largest real root of the cubic equation z3+2z2+(6χ−7)z+18χ−24=0z3+2z2+(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χ≤0, and a further improvement for graphs with large girth.