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

Henning, Michael A.; Vestergaard, Preben Dahl

Util. Math. 74, 187-197 (2007).

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.

MSC:

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

Keywords:

domination; packing number; paired-domination number; perfect matching; trees

Citations:

Zbl 0997.05074