A note on domination and independence-domination numbers of graphs
Martin Milanič · Ars Mathematica Contemporanea · 2012
Vizing'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 < γ .