The bondage number of graphs on topological surfaces: degree-S vertices and the average degree

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. An orientable surface ${\mathbb{S}}_h$ of genus $h$, $h\ge 0$, is obtained from the sphere ${\mathbb{S}}_0$ by adding $h$ handles. A non-orientable surface ${\mathbb{N}}_q$ of genus $q$, $q\ge 1$, is obtained from the sphere by adding $q$ crosscaps. The Euler characteristic of a surface is defined by $\chi ({\mathbb{S}}_h)=2-2h$ and $\chi ({\mathbb{S}}_q)=2-q$. Let $G$ be a connected graph of order $n$ which is 2-cell embedded on a surface $\mathbb{M}$ with $\chi (\mathbb{M})=\chi$. We prove that $b(G)\le 7+i$ when $\mathbb{M}={\mathbb{N}}_i$, $i=1,2,3$, and $b(G)\le 12$ when $\mathbb{M}\in \{{\mathbb{N}}_4,{\mathbb{S}}_2\}$. We give new arguments that improve the known upper bounds on the bondage number at least when $-7\chi /(\delta (G)-5)<n\le -12\chi$, $\delta (G)\ge 6$, where $\delta (G)$ is the minimum degree of $G$. We obtain sufficient conditions for the validity of the inequality $b(G)\le 2s-2$, provided $G$ has degree $s$ vertices. In particular, we prove that if $\delta (G)=\delta \ge 6$, $\chi \le -1$ and $-14\chi <\delta -4+2(\delta -5)n$ then $b(G)\le 2\delta -2$. We show that if $\gamma (G)=\gamma \ne 2$, where $\gamma (G)$ is the domination number of $G$, then $n\ge \gamma +(1+\sqrt{9+8\gamma -8\chi })/2$; the bound is tight. We also present upper bounds for the bondage number of graphs in terms of the girth, domination number and Euler characteristic. As a corollary we prove that if $\gamma (G)\ge 4$ and $\chi \le -1$, then $b(G)\le 11-24\chi /(9+\sqrt{41-8\chi })$. Several unanswered questions are posed.

arXiv comment17 pages, 3 figures

References in corpus (2)

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