Milanič, Martin A note on domination and independence-domination numbers of graphs. (English) Zbl 1301.05253 Ars Math. Contemp. 6, No. 1, 89-97 (2013). Summary: Vizing’s conjecture is true for graphs \( G \) satisfying \( \gamma^i( G ) = {\gamma} ( G )\), where \( \gamma ( G )\) is the domination number of a graph \( G \) and \( {\gamma} ^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 \( \gamma^i( G ) = {\gamma} ( 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 \( {\gamma} ^i( G ) = \gamma ( G ) = 2\) and of verifying whether \( \gamma^i( G ) \geq 2\) are NP-complete, even if \( G \) is weakly chordal. We also initiate the study of the equality \( {\gamma} ^i = \gamma \) in the context of hereditary graph classes and exhibit two infinite families of graphs for which \( \gamma ^i < {\gamma} \). Cited in 1 Document MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C17 Perfect graphs 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Keywords:Vizing’s conjecture; domination number; independence-domination number; weakly chordal graph; NP-completeness; hereditary graph class; IDD-perfect graph PDFBibTeX XMLCite \textit{M. Milanič}, Ars Math. Contemp. 6, No. 1, 89--97 (2013; Zbl 1301.05253) Full Text: DOI