Upper bounds on the bondage number of a graph

Vladimir Dimitrov Samodivkin

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. We obtain sufficient conditions for the validity of the inequality $b(G) \leq 2s - 2$, provided $G$ has degree s vertices. 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 give a stronger bound than the known constant upper bounds for the bondage number of graphs having domination number at least four. Several unanswered questions are posed.


Keywords


bondage number, domination number, Euler's formula, girth, average degree

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2018.6.1.1

Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats