Paired and inducedpaired domination in (E,net)free graphs
Schaudt, Oliver
(2011)
Paired and inducedpaired domination in (E,net)free graphs.
Technical Report
, 11 p.
Abstract
A dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many wellstudied variants of domination are the socalled paireddominating sets. A paireddominating set is a dominating set whose induced subgraph has a perfect matching. In this paper, we continue their study. We focus on graphs that do not contain the netgraph (obtained by attaching a pendant vertex to each vertex of the triangle) or the Egraph (obtained by attaching a pendant vertex to each vertex of the path on three vertices) as induced subgraphs. This graph class is a natural generalization of (claw,net)free graphs, which are intensively studied with respect to their nice properties concerning domination and hamiltonicity. We show that any connected (E,net)free graph has a paireddominating set that, roughly, contains at most half of the vertices of the graph. This bound is a significant improvement to the known general bounds. Further, we show that any (E,net, C_5 )free graph has an induced paireddominating set, that is a paireddominating set that forms an induced matching, and that such set can be chosen to be a minimum paireddominating sets. We use these results to obtain a new characterization of (E,net, C_5 )free graphs in terms of the hereditary existence of induced paireddominating sets. Finally, we show that the induced matching formed by an induced paireddominating set in a (E,net, C_5 )free graph can be chosen to have at most two times the size of the smallest maximal induced matching possible.
Download: 
Postscript
Download (599kB)  Preview 

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

Citations:  No citation data. 
Uncontrolled Keywords:  domination paireddomination induced paireddomination induced matchings (E, net)free graphs 
Subjects: 

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

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/619 