Remarks on the bondage number of planar graphs |
| |
Authors: | Miranca Fischermann Dieter Rautenbach Lutz Volkmann |
| |
Institution: | Lehrstuhl II für Mathematik, RWTH Aachen, 52056, Aachen, Germany |
| |
Abstract: | The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. In 1998, J.E. Dunbar, T.W. Haynes, U. Teschner, and L. Volkmann posed the conjecture b(G)Δ(G)+1 for every nontrivial connected planar graph G. Two years later, L. Kang and J. Yuan proved b(G)8 for every connected planar graph G, and therefore, they confirmed the conjecture for Δ(G)7. In this paper we show that this conjecture is valid for all connected planar graphs of girth g(G)4 and maximum degree Δ(G)5 as well as for all not 3-regular graphs of girth g(G)5. Some further related results and open problems are also presented. |
| |
Keywords: | Planar graphs Bondage number |
本文献已被 ScienceDirect 等数据库收录! |
|