A note on connected dominating sets of distance-hereditary graphs

Schaudt, Oliver (2011) A note on connected dominating sets of distance-hereditary 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 distance-hereditary 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 distance-hereditary graphs in the following sense: If G is a connected distance-hereditary 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 distance-hereditary graph without dominating vertex has minimal size. In other words, connected distance-hereditary graphs without dominating vertex are connected well-dominated. Furthermore, we show that if G is a distance-hereditary 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] .


Actions:
Download: [img] Postscript
Download (467Kb) | Preview
Download: [img] PDF
Download (80Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2011-620
Depositing User: Oliver Schaudt
Date Deposited: 17 May 2011 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/620