























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 $χ$ is as large as possible, and assume $χ\leq0$. Gagarin-Zverovich and Huang have recently found upper bounds of $b(G)$ in terms of the maximum degree $Δ(G)$ and the Euler characteristic $χ(G)=χ$. In this paper we prove a better upper bound $b(G)\leqΔ(G)+\lfloor t\rfloor$ where $t$ is the largest real root of the cubic equation $z^3 + z^2 + (3χ- 8)z + 9χ- 12=0$; this upper bound is asymptotically equivalent to $b(G)\leqΔ(G)+1+\lfloor \sqrt{4-3χ} \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 $χ$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。