Distance-2 Independent Domination Numbers

Abstract

The distance d(u,v) between two vertices u and v in a graph G equals the length of a shortest path from u to v. A distance-2 independent set of a graph G is a subset I of the vertices such that the distance between any two vertices of I in G is at least three. A set S of vertices is called a distance-2 dominating set if every vertex in V \ S is within distance-2 of at least one member of S. A distance-2 independent dominating set of G is both a distance-2 dominating set and a distance-2 independent set of G. The distance-2 independent domination number, denoted by ( ) 2 i G , of a graph G is the minimum cardinality among all distance-2 independent dominating sets of G. A distance-2 independent dominating set I of G called an 2 i -set if | | ( ) 2 I  i G . Let I be an 2 i -set of a tree T and zI . If 1 x and 2 x are two distinct leaves adjacent to the same support vertices z in T, then ' { } 2 T  T  x is a tree and ( ') ( ) 2 i T  i T . If P : x ,y , z 1 1 and P': x ,y , z 2 2 are two end-path of a tree T, then '' { , } 2 2 T  T  x y is a tree and ( '') ( ) 2 i T  i T . Hence we consider the weak-trees. A weak-tree is a tree such that every vertex is adjacent at most one leaf and at most one support vertex. Let ï‡(n) be the sets of all weak-trees T ~ with i T )  n ~ ( 2 . In this paper, we determine the maximum order | ~ |T among all T ~ ï‡(n) .