A Graph Class related to the Structural Domination Problem

Schaudt, Oliver (2010) A Graph Class related to the Structural Domination Problem.
Technical Report , 12 p.


In the structural domination problem one is concerned with the question if a given graph has a connected dominating set whose induced subgraph has certain structural properties. For most of the common graph properties, the associated decision problem is NP-hard. Recently, BacsĂ´ and Tuza gave a full characterization of the graphs whose every induced subgraph has a connected dominating set satisfying an arbitrary prescribed hereditary property. Using the Theorem of BacsĂ´ and Tuza, we derive a finite forbidden subgraph characterization of the distance-hereditary graphs that have a dominating induced tree. Furthermore, we show that for distance-hereditary graphs minimum dominating induced trees can be found efficiently. The main part of the paper studies a new class of graphs, the extit{structural domination class}, which is closely related to the structural domination problem. Among other results, we give new characterizations of certain subclasses of distance-hereditary graphs (in particular for ptolemaic graphs) and analyse the structure of minimum connected dominating sets of structural domination graphs. It turns out that many of the problems associated to structural domination become tractable on the hereditary part of the structural domination class.

Download: [img] Postscript
Download (624kB) | Preview
Download: [img] PDF
Download (146kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2010-607
Depositing User: Oliver Schaudt
Date Deposited: 08 Jun 2011 00:00
Last Modified: 09 Jan 2012 14:16
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/607