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

Original · EN

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)≤{Δ(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 z³+2z²+(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.