Perfect graphs of strong domination and independent strong domination
type: Item
instance of: scholarly article
title: Perfect graphs of strong domination and independent strong domination
zbMATH Open document ID: 0972.05037
DOI: 10.1016/S0012-365X(00)00116-3
author: Dieter Rautenbach
author: Vadim Zverovich
published in: Discrete Mathematics
publication date: 2001-11-07T00:00:00Z
review text: A graph \(G\) is called domination perfect if for every induced subgraph \(H\) of \(G\) the domination number of \(H\) equals the independent domination number of \(H\). Such equalities among four parameters, namely domination number, strong domination number, independent domination number and independent strong domination number, lead to six possible perfection classes of graphs, several subclasses of which are characterized in this paper via forbidden induced subgraphs. Furthermore it is shown that the problems of deciding whether for a given graph \(G\) and a given integer \(k\) there is a strong dominating set, independent strong dominating set, or weak dominating set, of \(G\) of cardinality at most \(k\) are NP-complete. Several open problems and conjectures are proposed.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C17
zbMATH DE Number: 1565947
zbMATH Keywords: domination
zbMATH Keywords: strong domination
zbMATH Keywords: independent strong domination
zbMATH Keywords: perfect
zbMATH Keywords: forbidden induced subgraph characterization
zbMATH Keywords: complexity
reviewed by: Herman J. Servatius
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1565947