Upper Bounds on the Bondage Number of a Graph

Vladimir Dimitrov Samodivkin

Download full text
(English, 16 pages)

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.

Metrics

  • 124 views
  • 67 downloads

Journal

Electronic Journal of Graph Theory and Applications

The Electronic Journal of Graph Theory and Applications (EJGTA) is a refereed journal devoted to ... see more