Bipartite Domination in Outerplanar Graphs
摘要
For a graph \(G=(V(G),E(G))\) , a dominating set of G is a set \(S\subseteq V(G)\) such that every vertex in G is either in S or adjacent to a vertex in S. A bipartite dominating set of G is a dominating set \(S\subseteq V(G)\) such that the induced subgraph G[S] is bipartite. The bipartite domination number of G, denoted \(\gamma _{bip}(G)\) , is the minimum size of a bipartite dominating set of G. This concept was first initiated by Bachstein, Goddard and Henning [Math. Pannon. (N.S.), 2022]. Currently, there is not much research on this concept. And Bachstein et al. suggested that it would be interesting to determine further results on planar graphs in general or subsets thereof. Motivated by this, we continue to study on bipartite domination numbers of the outerplanar graphs in this paper. The main result is stated as follows: If G is a 2-connected outerplanar graph of order \(n \ge 3\) , then \(\gamma _{bip}(G)\le \lceil n/3\rceil \) . Moreover, we constructed an infinite family of 2-connected outerplanar graphs achieving this bound.