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^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> </mml:math> 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^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> </mml:math> is the maximum size of an independent set in $$G^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> </mml:math> . The chromatic number of $$G^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> </mml:math> , $$\chi (G^k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>χ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , is the smallest number of colors needed to color $$G^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> </mml:math> so that the vertices sharing the same color form an independent set of $$G^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> </mml:math> . In this paper, we study the independence number of $$G^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> </mml:math> , 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^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> </mml:math> . 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 ( $$\chi (G^k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>χ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> )-coloring of $$G^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>G</mml:mi> <mml:mi>k</mml:mi> </mml:msup> </mml:math> .