Paired- and induced paired-domination in (E,net)-free graphs
Oliver Schaudt · Discussiones Mathematicae Graph Theory · 2012
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 paireddominating 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 set.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.