A note on domination and independence-domination numbers of graphs

Martin Milanič

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.

Full Text:

PDF ABSTRACTS (EN/SI)


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