On the independence number of graph powers

Let G be a simple connected graph, and k be a positive integer. The k th graph power Gᵏ G k of G is the graph whose vertex set is the vertex set of G and two distinct vertices are adjacent if and only if their distance in G is at most k . The independence number of Gᵏ G k is the maximum size of an independent set in Gᵏ G k . The chromatic number of Gᵏ G k , χ (Gᵏ) χ ( G k ) , is the smallest number of colors needed to color Gᵏ G k so that the vertices sharing the same color form an independent set of Gᵏ G k . In this paper, we study the independence number of Gᵏ G k , when G is a tree, by giving a known lower bound for the number of vertices that a tree must have, assuming a certain independence number of Gᵏ G k . As a consequence of our proof, we describe all trees that attain this lower bound. For some of the trees given G , we also describe a ( χ (Gᵏ) χ ( G k ) )-coloring of Gᵏ G k .