The clique number of the exact distance <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e4357" altimg="si12.svg"><mml:mi>t</mml:mi></mml:math>-power graph: Complexity and eigenvalue bounds

The exact distance t -power of a graph G , G [ ♯ t ] , is a graph which has the same vertex set as G , with two vertices adjacent in G [ ♯ t ] if and only if they are at distance exactly t in the original graph G . We study the clique number of this graph, also known as the t -equidistant number. We show that it is NP-hard to determine the t -equidistant number of a graph, and that in fact, it is NP-hard to approximate it within a constant factor. We also investigate how the t -equidistant number relates to another distance-based graph parameter; the t -independence number. In particular, we show how large the gap between both parameters can be. The hardness results motivate deriving eigenvalue bounds, which compare well against a known general bound. In addition, the tightness of the proposed eigenvalue bounds is studied.