Abstract
A total dominating set of a graph G with no isolated vertex is a set S of vertices of G such that every vertex is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. A paired-dominating set of G 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. Since every paired-dominating set is a total dominating set, the total domination number is bounded above by the paired-domination number. We give a constructive characterization of the trees with equal total domination and paired-domination numbers. Our characterization uses labelings of the vertices that indicates the roles each vertex plays in the sets associated with both parameters.
| Original language | English |
|---|---|
| Pages (from-to) | 207-218 |
| Number of pages | 12 |
| Journal | Utilitas Mathematica |
| Volume | 69 |
| Publication status | Published - Mar 2006 |
| Externally published | Yes |
Keywords
- Paired-domination
- Total domination
- Trees
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics