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

Abstract

For a graph G , the distance between two vertices u and v in G equals the minimum length of a u-v path. A vertex-subset D is a distance-3 dominating set if every vertex not belonging to D is at distance at most three of a vertex in D . The distance-3 domination number ( ) 3 g G of a graph G is the minimum cardinality of a distance-3 dominating set in G . Here we consider the trees. Let G(n) be the set of trees T satisfying (T)=n 3 g , where n ³ 1 . In this paper, we provide a constructive characterization of G(n) for all n ³ 1.