A note on domination and independence-domination numbers of graphs
Keywords:Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph.
AbstractVizing's conjecture is true for graphs G satisfying γi(G) = γ(G), where γ(G) is the domination number of a graph G and γi(G) is the independence-domination number of G, that is, the maximum, over all independent sets I in G, of the minimum number of vertices needed to dominate I. The equality γi(G) = γ(G) is known to hold for all chordal graphs and for chordless cycles of length 0 (mod 3). We prove some results related to graphs for which the above equality holds. More specifically, we show that the problems of determining whether γi(G) = γ(G) = 2 and of verifying whether γi(G) ≥ 2 are NP-complete, even if G is weakly chordal. We also initiate the study of the equality γi = γ in the context of hereditary graph classes and exhibit two infinite families of graphs for which γi < γ.
Special Issue Bled'11
Articles in this journal are published under Creative Commons Attribution 4.0 International License