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


Abstract in English

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 $chileq0$. 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)leqDelta(G)+lfloor trfloor$ where $t$ is the largest real root of the cubic equation $z^3 + z^2 + (3chi - 8)z + 9chi - 12=0$; this upper bound is asymptotically equivalent to $b(G)leqDelta(G)+1+lfloor sqrt{4-3chi} 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$.

Download