A note on connected dominating sets of distancehereditary graphs
Schaudt, Oliver
(2011)
A note on connected dominating sets of distancehereditary graphs.
Technical Report
, 5 p.
Abstract
A vertex subset of a graph is a dominating set if every vertex of the graph belongs to the set or has a neighbor in it. A connected dominating set is a dominating set such that the induced subgraph of the set is a connected graph. A graph is called distancehereditary if every induced path is a shortest path. In this note, we give a complete description of the (inclusionwise) minimal connected dominating sets of connected distancehereditary graphs in the following sense: If G is a connected distancehereditary graph that has a dominating vertex, any minimal connected dominating set is a single vertex or a pair of two adjacent vertices. If G does not have a dominating vertex, the subgraphs induced by any two minimal connected dominating sets are isomorphic. In particular, any inclusionwise minimal connected dominating set of a connected distancehereditary graph without dominating vertex has minimal size. In other words, connected distancehereditary graphs without dominating vertex are connected welldominated. Furthermore, we show that if G is a distancehereditary graph that has a minimal connected dominating set X of size at least 2, then for any connected induced subgraph H it holds that the subgraph induced by any minimal connected dominating set of H is isomorphic to an induced subgraph of G[X] .
Download: 
Postscript
Download (478kB)  Preview 

Download: 
PDF
Download (82kB)  Preview 
Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  0 (Google Scholar)  
Uncontrolled Keywords:  connected dominating sets distancehereditary graphs 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle 
Related URLs: 
ZAIK Number:  zaik2011620 

Depositing User:  Oliver Schaudt 
Date Deposited:  17 May 2011 00:00 
Last Modified:  19 Dec 2011 09:44 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/620 