Trees with equal 2-domination and 2-independence numbers
Mustapha Chellali, Nacéra Meddah · Discussiones Mathematicae Graph Theory · 2012
Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number 2(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number �2(G). Fink and Jacobson proved that 2(G) � �2(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.