×

A note on domination and independence-domination numbers of graphs. (English) Zbl 1301.05253

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} \).

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.)
PDFBibTeX XMLCite
Full Text: DOI