New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic

Abstract

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. Let $G$ be embeddable on a surface whose Euler characteristic $\chi$ is as large as possible, and assume $\chi \le 0$. Gagarin-Zverovich and Huang have recently found upper bounds of $b(G)$ in terms of the maximum degree $\Delta (G)$ and the Euler characteristic $\chi (G)=\chi$. In this paper we prove a better upper bound $b(G)\le \Delta (G)+\lfloor t\rfloor$ where $t$ is the largest real root of the cubic equation $z^3+z^2+(3\chi -8)z+9\chi -12=0$; this upper bound is asymptotically equivalent to $b(G)\le \Delta (G)+1+\lfloor \sqrt{4-3\chi }\rfloor$. We also establish further improved upper bounds for $b(G)$ when the girth, order, or size of the graph $G$ is large compared with its Euler characteristic $\chi$.

11 pages. arXiv admin note: text overlap with arXiv:1111.5629