Upper bounds on the bondage number of a graph
| Main Author: | Samodivkin, Vladimir Dimitrov; Departments of Mathematics, University of Architecture, Civil Engineering and Geodesy, Sofia, Bulgaria |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2018
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/129 https://www.ejgta.org/index.php/ejgta/article/view/129/pdf_54 |
Daftar Isi:
- 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) ≤ 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.