Universität zu Köln

Schaudt, Oliver (2011). A note on connected dominating sets of distance-hereditary graphs. Working Paper.

Preview

PDF zaik2011-620.pdf Download (82kB) | Preview

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 GX .

Item Type:	Preprints, Working Papers or Reports (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550113
Date:	May 2011
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/55011