Total Domination and Open Packing in Two Subclasses of Triangle-Free Graphs
摘要
A vertex subset D of a graph G(V, E) is called a total dominating set if every vertex in G has a neighbor in D, and a vertex subset S of G is called an open packing in G if no pair of distinct vertices in S have a common neighbor in G. The size of a minimum total dominating set (resp. maximum open packing) in G is called the total domination number (resp. open packing number) of G and is denoted by \(\gamma _t(G)\) (resp. \(\rho ^o(G)\) ). Notably, the open packing number is a lower bound for the total domination number in graphs with no isolated vertices [Henning and Slater, 1999]. Given a graph G and a positive integer k, Total Dominating Set problem decides whether \(\gamma _t(G)\le k\) and Open Packing problem tests whether \(\rho ^o(G)\ge k\) . In this work, we study the complexity of the problems Total Dominating Set and Open Packing in two subclasses of \(K_3\) -free graphs: \(\{P_6,C_6,K_3\}\) -free graphs and triangle-free cubic planar graphs. We prove that in a connected \(\{P_6,C_6,K_3\}\) -free graph, every minimum total dominating set is a biclique. We use this result to prove that (i) for a connected \(\{P_6,C_6,K_3\}\) -free graph G, \(\gamma _t(G)\le \rho ^o(G)+1\) and (ii) a minimum total dominating set and a maximum open packing in a \(\{P_6,C_6,K_3\}\) -free graph can be found in \(O(n^4)\) time. We also show that for a connected \(\{P_6,C_6,K_3\}\) -free graph G, \(\gamma _t(G)=\rho ^o(G)\) if and only if at least one vertex of G is not contained in any \(C_5\) of G. In contrast to the above set of polynomial-time algorithm and structural characterization, we prove that Total Dominating Set and Open Packing are NP-complete on triangle-free cubic planar graphs.