On Paired and Double Domination in Graphs
Document Type
Article
Publication Date
5-1-2005
Description
A paired dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, and a double dominating set is a dominating set that dominates every vertex of G at least twice. First a necessary and sufficient condition is given for a double dominating set (respectively, paired dominating set) to be minimal in G. We show that for clawfree graphs, the paired domination number is less than or equal to the double domination number. Then bounds on the double and paired domination numbers are presented. Sums involving these parameters are also considered.
Citation Information
Chellali, Mustapha; and Haynes, Teresa W.. 2005. On Paired and Double Domination in Graphs. Utilitas Mathematica. Vol.67 161-171. ISSN: 0315-3681