On the independence number of graph powers

Abstract 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.