Independent domination and matchings in graphs (Q1861228): Difference between revisions

The minimum (maximum) cardinality of a maximal independent set of a graph \(G\) is the independent domination number (respectively, independence number) and is denoted by \(i(G)\) (respectively, \(\alpha(G)\)). The maximum cardinality of a matching of \(G\) is denoted by \(\alpha_0(G)\). Every graph \(G\) satisfies the sequence of inequalities: \(i(G) \leq \alpha(G) \leq \alpha_0(G)\). The authors characterise the class of graphs \(G\) for which \(i(G) + \alpha_0(G) = |V(G)|\) and develop a polynomial algorithm for recognising this class of graphs.