A Constructive Characterization of Trees with the Same Distance-2 Domination Number

The distance between two vertices and in a graph equalsthe length of a shortest path from to . A set of verticesis distance-2 dominating if every vertex not belonging to is atdistance at most two of a vertex in .The distance-2 domination number of a graph , denoted by , is the minimum cardinality of adistance-2 dominating setin .Notethat in general to determine the number in a graph Gis NP-complete even if G is bipartite [4]. Here we focus on the trees. For , let be the set of trees satisfying . In thispaper, we provide a constructive characterization of for all . Index Terms - Distance-2 Dominating Set, Distance-2 Domination Number.