An improved upper bound for bondage number of graphs on surfaces

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

2011-11-23

arxiv.org/abs/1111.5629v2

Mathematics

Combinatorics

An improvement for graphs with large girth added

Scientific paper

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 [arXiv: 1012.4117] 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)\leq\min\{\Delta(G)+h+2,\Delta+k+1\}$. Using the Euler characteristic $\chi$ instead of the genera $h$ and $k$, with the relations $\chi=2-2h$ and $\chi=2-k$, we establish an improved upper bound $b(G)\leq\Delta(G)+\lfloor r\rfloor$ for the case $\chi\leq0$ (i.e. $h\geq1$ or $k\geq2$), 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)\leq\Delta(G)+\lceil\sqrt{12-6\chi\,}-1/2\rceil$ for $\chi\leq0$, and a further improvement for graphs with large girth.

Affiliated with

Also associated with

No associations

Rating

An improved upper bound for bondage number of graphs on surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An improved upper bound for bondage number of graphs on surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An improved upper bound for bondage number of graphs on surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-155895