We study the problem of the existence of perfect (1,2)-dominating sets in graphs. A perfect (1,2)-dominating set is a (1, 2)-dominating set that is not double dominating and has the property that every vertex outside the set has exactly one neighbor in it. While previous work focused mainly on graphs with large maximum degree, we investigate perfect (1,2)-dominating sets in graphs of small degree, namely subcubic graphs and 4-regular graphs. We prove that every connected subcubic graph which is not isomorphic to one of the graphs in the family \(\{K_1,K_2,K_3,K_4, K_4^-\}\) admits a perfect (1,2)-dominating set, and such a set can be constructed in polynomial time. For 4-regular graphs, we provide a characterization in terms of induced 3-regular subgraphs, and show that the problem of deciding the existence of a perfect (1,2)-dominating set is NP-complete. Finally, we extend the study to independent perfect (1,2)-dominating sets in cubic planar graphs, establishing a direct relation with 1-perfect codes. In particular, we show that deciding whether a cubic planar graph contains such a set is NP-complete.

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

Complexity of Perfect (1, 2)-Dominating Sets in Low-Degree Graphs

  • Urszula Bednarz,
  • Jan Kratochvíl,
  • Adrian Michalski

摘要

We study the problem of the existence of perfect (1,2)-dominating sets in graphs. A perfect (1,2)-dominating set is a (1, 2)-dominating set that is not double dominating and has the property that every vertex outside the set has exactly one neighbor in it. While previous work focused mainly on graphs with large maximum degree, we investigate perfect (1,2)-dominating sets in graphs of small degree, namely subcubic graphs and 4-regular graphs. We prove that every connected subcubic graph which is not isomorphic to one of the graphs in the family \(\{K_1,K_2,K_3,K_4, K_4^-\}\) admits a perfect (1,2)-dominating set, and such a set can be constructed in polynomial time. For 4-regular graphs, we provide a characterization in terms of induced 3-regular subgraphs, and show that the problem of deciding the existence of a perfect (1,2)-dominating set is NP-complete. Finally, we extend the study to independent perfect (1,2)-dominating sets in cubic planar graphs, establishing a direct relation with 1-perfect codes. In particular, we show that deciding whether a cubic planar graph contains such a set is NP-complete.