The Bondage Number of Graphs with Crossing Number Less than Four

Abstract

The bondage number \(b(G)\) of a graph \(G\) is the smallest number of edges whose removal results in a graph with domination number greater than the domination number of \(G\). Kang and Yuan [Bondage number of planar graphs. Discrete Math. \(222 (2000), 191-198]\) proved \(b(G) \leq \min\{8, \Delta + 2\}\) for every connected planar graph \(G\), where \(\Delta\) is the maximum degree of \(G\). Later Carlson and Develin [On the bondage number of planar and directed graphs. Discrete Math. \(306 (8-9) (2006), 820-826]\) presented a method to give a short proof for this result. This paper applies this technique to generalize the result of Kang and Yuan to any connected graph with crossing number less than four.