A note on domination and independence-domination numbers of graphs

Martin Milanič

Ars Mathematica Contemporanea, Tome 6 (2013) no. 1, pp. 89-97.

Résumé

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 γ.

Détail

DOI : 10.26493/1855-3974.282.71c

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