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

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. 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)\le \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)\le \Delta (G)+\lfloor r\rfloor$ for the case $\chi \le 0$ (i.e. $h\ge 1$ or $k\ge 2$), 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)\le \Delta (G)+\lceil \sqrt{12-6\chi }-1/2\rceil$ for $\chi \le 0$, and a further improvement for graphs with large girth.

8 pages, to appear in Discrete Mathematics

References in corpus (1)

• Upper bounds for the bondage number of graphs on topological surfaces

Cited by in corpus (2)

• On Bondage Numbers of Graphs -- a survey with some comments
• The bondage number of graphs on topological surfaces: degree-S vertices and the average degree