Independent domination and matchings in graphs
type: Item
instance of: scholarly article
title: Independent domination and matchings in graphs
zbMATH Open document ID: 1015.05064
DOI: 10.1016/S0012-365X(02)00304-7
author: Dieter Rautenbach
author: Lutz Volkmann
published in: Discrete Mathematics
publication date: 2003-03-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1882165
zbMATH Keywords: independent domination
zbMATH Keywords: matching
zbMATH Keywords: 2-satisfiability
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00304-7
OpenAlex ID: W2084029063
description: scientific article; zbMATH DE number 1882165