Paired and induced-paired domination in (E,net)-free graphs
Paired and induced-paired domination in (E,net)-free graphs.
Technical Report , 11 p.
A dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many well-studied variants of domination are the so-called paired-dominating sets. A paired-dominating 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 net-graph (obtained by attaching a pendant vertex to each vertex of the triangle) or the E-graph (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 paired-dominating 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 paired-dominating set, that is a paired-dominating set that forms an induced matching, and that such set can be chosen to be a minimum paired-dominating 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 paired-dominating sets. Finally, we show that the induced matching formed by an induced paired-dominating 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.
|Item Type:||Paper (Technical Report)|
|Citations:||No citation data.|
|Uncontrolled Keywords:||domination paired-domination induced paired-domination induced matchings (E, net)-free graphs|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
Mathematical Institute > Prof. Dr. Faigle
|Depositing User:||Oliver Schaudt|
|Date Deposited:||17 May 2011 00:00|
|Last Modified:||19 Dec 2011 09:44|