Trees with paired-domination number twice their domination number. (English) Zbl 1181.05070

Summary: We continue the study of paired-domination in graphs introduced by T. W. Haynes and P. J. Slater [Networks 32, No. 3, 199–206 (1998; Zbl 0997.05074)]. A paired-dominating set of a graph \(G\) with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of \(G\) is the minimum cardinality of a paired-dominating set of \(G\). For \(k\geq 2\), a \(k\)-packing in \(G\) is a set \(S\) of vertices of \(G\) that are pairwise at distance greater than \(k\) apart. The \(k\)-packing number of \(G\) is the maximum cardinality of a \(k\)-packing in \(G\). Haynes and Slater observed that the paired-domination number is bounded above by twice the domination number. We give a constructive characterization of the trees attaining this bound that uses labelings of the vertices. The key to our characterization is the observation that the trees with paired-domination number twice their domination number are precisely the trees with 2-packing number equal to their 3-packing number.


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees


Zbl 0997.05074