Abstract
A set S of vertices in a graph G is a 2-dominating set if every vertex of G not in S is adjacent to at least two vertices in S, and S is a 2-independent set if every vertex in S is adjacent to at most one vertex of S. The 2-domination number γ2(G) is the minimum cardinality of a 2-dominating set in G, and the 2-independence number α2(G) is the maximum cardinality of a 2-independent set in G. Chellali and Meddah [Trees with equal 2-domination and 2-independence numbers, Discussiones Mathematicae Graph Theory 32 (2012), 263-270] provided a constructive characterization of trees with equal 2-domination and 2-independence numbers. Their characterization is in terms of global properties of a tree, and involves properties of minimum 2-dominating and maximum 2-independent sets in the tree at each stage of the construction. We provide a constructive characterization that relies only on local properties of the tree at each stage of the construction.
Original language | English |
---|---|
Article number | 8050 |
Journal | Discrete Mathematics and Theoretical Computer Science |
Volume | 19 |
Issue number | 1 |
Publication status | Published - 2017 |
Keywords
- 2-domination
- 2-domination number
- 2-independence
- 2-independence number
- Tree
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
- Discrete Mathematics and Combinatorics