Abstract | ||
---|---|---|
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 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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.7151/dmgt.1617 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
domination,paired-domination,induced paired-domination,induced matchings,{E,net}-free graphs | Discrete mathematics,Dominating set,Combinatorics,Claw-free graph,Vertex (graph theory),Bipartite graph,Cycle graph,Neighbourhood (graph theory),Feedback vertex set,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
32 | 3 | 1234-3099 |
Citations | PageRank | References |
1 | 0.38 | 14 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Oliver Schaudt | 1 | 95 | 21.74 |