On the bondage number of planar and directed graphs (Q2495520): Difference between revisions

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 of \(G\). In 1998, \textit{J. E. Dunbar, T. Haynes, U. Teschner} and \textit{L. Volkmann} [Pure Appl. Math., Marcel Dekker. 209, 471--489 (1998; Zbl 0894.05025)] conjectured \(b(G) \leq \Delta(G) + 1\) for every nontrivial connected planar graph \(G\) whose maximum degree is \(\Delta(G)\). In this paper, the authors gave a nice simpler proof of Kang and Yuan's theorem \(b(G) \leq \min \{ 8, \Delta(G) + 2 \}\) for all connected planar graphs \(G\) [\textit{L. Kang} and \textit{J. Yuan}, Discrete Math. 222, No. 1--3, 191--198 (2000; Zbl 0961.05055)]. In particular, their new proof of \(b(G) \leq \Delta(G) + 2\) for any connected planar graph \(G\) is very neat. They also proved that \(b(G) \leq \Delta(G) + 3\) if \(G\) is connected and can be embedded on a torus. \textit{M. Fischermann, D. Rautenbach} and \textit{L. Volkmann} [Discrete Math. 260, No. 1--3, 57--67 (2003; Zbl 1009.05104)] asked whether there are planar graphs \(G\) with \(6 \leq b(G) \leq 8\). A class of planar graphs with bondge number \(6\) is constructed in this paper. For directed graphs, the authors proved that \(b(G) \leq \frac{3}{2}\Delta(G)\), and conjectured that \(b(G) \leq \Delta(G) + 1\).