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

Jia Huang

Published 2011-11-23, updated 2012-05-21Version 3

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 $\Delta(G)$ and embeddable on an orientable surface of genus $h$ and a non-orientable surface of genus $k$, $b(G)\leq\min\{\Delta(G)+h+2,\Delta+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 $\chi$ instead of the genera $h$ and $k$, with the relations $\chi=2-2h$ and $\chi=2-k$. We show that $b(G)\leq\Delta(G)+\lfloor r\rfloor$ for the case $\chi\leq0$ (i.e. $h\geq1$ or $k\geq2$), where $r$ is the largest real root of the cubic equation $z^3+2z^2+(6\chi-7)z+18\chi-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)\leq\Delta(G)+\lceil\sqrt{12-6\chi\,}-1/2\rceil$ for $\chi\leq0$, and a further improvement for graphs with large girth.