Abstract:
The set of vertices of a graph is called distance-$k$ independent if the distance between any two of its vertices is greater than some integer $k \geq 1.$ In this paper we describe $n$-vertex trees with a given diameter $d$ which have maximum and minimum possible number of distance-$k$ independent sets among all such trees. The maximum problem is solved for the case $1 < k < d \leq 5.$ The minimum problem is significantly more simple and is solved for all $1 < k < d < n.$ Illustr. 4, bibliogr. 10.