| Article ID: | iaor20116924 |
| Volume: | 22 |
| Issue: | 2 |
| Start Page Number: | 217 |
| End Page Number: | 234 |
| Publication Date: | Aug 2011 |
| Journal: | Journal of Combinatorial Optimization |
| Authors: | Henning A, Southey Justin |
| Keywords: | graph partitioning |
A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired‐dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set and the subgraph induced by the set contains a perfect matching. In this paper, we provide a constructive characterization of graphs whose vertex set can be partitioned into a dominating set and a paired‐dominating set.