A characterization of domination reducible graphs
type: Item
instance of: scholarly article
title: A characterization of domination reducible graphs
zbMATH Open document ID: 1055.05117
published in: Graphs and Combinatorics
publication date: 2004-12-13T00:00:00Z
review text: Let \(G=(V,E)\) be a graph. A set \(D\subseteq V(G)\) is dominating in \(G\) if every vertex of \(V(G)\setminus D\) is adjacent to some vertex of \(D\). The minimum cardinality of a dominating set in \(G\) is called the domination number of \(G\). And a set \(W\subseteq V(G)\) is called homogeneous in \(G\) if (a) \(2\leq|W|\leq|V(G)|-1\), and (b) \(N(x)\setminus W=N(y)\setminus W\) for each \(x,y\in W\), where \(N(v)\) denotes the neighborhood of vertex \(v\) in \(C\) (Definition 1). Moreover \(G\) is called a domination reducible graph if every induced subgraph \(H\) of \(G\) satisfies at least one of the following conditions: (a) \(\overline H\) is a disconnected graph, (b) \(H\) is a disconnected graph, (c) there is a dominating set \(D\subseteq V(H)\) of order 4 that induces \(P_4\), or (d) \(H\) has a homogeneous set \(W\) that is not simple (Definition 2). The author introduces a hereditary class of domination reducible graphs and he proves that the problem of finding the minimum dominating set is polynomial-time solvable (Proposition 1). To characterize this class structurally the author uses additional concepts (Definitions 3, 4 and 5), e.g. the concept of a reducing \(W\)-pseudopath, and together with the application of a theorem of himself in an other publication (in the present paper: Theorem 2) he gets by an extensive proof the main result of the paper by a characterization by forbidden subgraphs, namely Theorem 1: A graph \(G\) is a domination reducible graph if and only if \(G\) has no induced subgraphs isomorphic to \(G_1,G_2,\dots,G_6\), whose figures are given in the present paper. Finally two conjectures are formulated. Conjecture 1: The maximum stable set problem for domination reducible graphs can be solved in polynomial time. And the more general Conjecture 2 reads: Let \({\mathfrak P}\) be a hereditary class. If the minimum dominating set problem for \({\mathfrak P}\) can be solved in polynomial time then the maximum stable set problem for \({…
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 2121767
zbMATH Keywords: domination number
zbMATH Keywords: hereditary class of graphs
zbMATH Keywords: forbidden induced subgraphs
zbMATH Keywords: homogeneous set
author: I.È. Zverovich
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: s00373-003-0541-0
OpenAlex ID: W2013267996
DOI: 10.1007/S00373-003-0541-0
description: scientific article; zbMATH DE number 2121767