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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Bipartite Domination in Outerplanar Graphs

  • Changqing Xi,
  • Jun Yue

摘要

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.