A note on domination and independence-domination numbers of graphs

Abstract

Vizing's conjecture is true for graphs G satisfying γⁱ(G) = γ(G), where γ(G) is the domination number of a graph G and γⁱ(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 γⁱ(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 γⁱ(G) = γ(G) = 2 and of verifying whether γⁱ(G) ≥ 2 are NP-complete, even if G is weakly chordal. We also initiate the study of the equality γⁱ = γ in the context of hereditary graph classes and exhibit two infinite families of graphs for which γⁱ < γ.