A dominating set of a graph G is a subset S of its vertices such that each vertex of G not in S has a neighbor in S. A face-hitting set of a plane graph G is a set T of vertices in G such that every face of G contains at least one vertex of T. We show that the vertex-set of every plane (multi-)graph without isolated vertices, self-loops or 2-faces can be partitioned into two disjoint sets so that both the sets are dominating and face-hitting. We also show that all the three assumptions above are necessary for the conclusion. As a corollary, we show that every n-vertex simple plane triangulation has a dominating set of size at most \((1 - \alpha )n/2\) , where \(\alpha n\) is the maximum size of an independent set in the triangulation. Matheson and Tarjan [European J. Combin., 1996] conjectured that every plane triangulation with a sufficiently large number of vertices n has a dominating set of size at most n/4. Currently, the best known general bound for this is by Christiansen, Rotenberg and Rutschmann [6] [SODA, 2024] who showed that every plane triangulation on \(n > 10\) vertices has a dominating set of size at most 2n/7. Our corollary improves their bound for n-vertex plane triangulations which contain a maximal independent set of size either less than 2n/7 or more than 3n/7.

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

Face-Hitting Dominating Sets in Planar Graphs

  • P. Francis,
  • Abraham M. Illickan,
  • Lijo M. Jose,
  • Deepak Rajendraprasad

摘要

A dominating set of a graph G is a subset S of its vertices such that each vertex of G not in S has a neighbor in S. A face-hitting set of a plane graph G is a set T of vertices in G such that every face of G contains at least one vertex of T. We show that the vertex-set of every plane (multi-)graph without isolated vertices, self-loops or 2-faces can be partitioned into two disjoint sets so that both the sets are dominating and face-hitting. We also show that all the three assumptions above are necessary for the conclusion. As a corollary, we show that every n-vertex simple plane triangulation has a dominating set of size at most \((1 - \alpha )n/2\) , where \(\alpha n\) is the maximum size of an independent set in the triangulation. Matheson and Tarjan [European J. Combin., 1996] conjectured that every plane triangulation with a sufficiently large number of vertices n has a dominating set of size at most n/4. Currently, the best known general bound for this is by Christiansen, Rotenberg and Rutschmann [6] [SODA, 2024] who showed that every plane triangulation on \(n > 10\) vertices has a dominating set of size at most 2n/7. Our corollary improves their bound for n-vertex plane triangulations which contain a maximal independent set of size either less than 2n/7 or more than 3n/7.