### A note on domination and independence-domination numbers of graphs

#### Abstract

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}<*γ*.#### Keywords

Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph.

DOI: https://doi.org/10.26493/1855-3974.282.71c

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications