Mathematics – Combinatorics
Scientific paper
2010-12-18
Mathematics
Combinatorics
10 pages; Updated version (April 2011); Presented at the 7th ECCC, Wolfville (Nova Scotia, Canada), May 4-6, 2011, and the 23r
Scientific paper
10.1016/j.disc.2011.10.018
The bondage number b(G) of a graph G is the smallest number of edges of G whose removal from G results in a graph having the domination number larger than that of G. We show that, for a graph G having the maximum vertex 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(G)+k+1\}$. This generalizes known upper bounds for planar and toroidal graphs.
Gagarin Andrei
Zverovich Vadim
No associations
LandOfFree
Upper bounds for the bondage number of graphs on topological 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 Upper bounds for the bondage number of graphs on topological surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Upper bounds for the bondage number of graphs on topological surfaces will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-725412