Location: MF 13

Speaker: Luuk Reijnders (TU/e, former master student)

Title: The clique number of the exact distance t-power graph: complexity and eigenvalue bounds

Abstract: 
The exact distance t-power of a graph G is a graph which has the same vertex set as G, with two vertices adjacent 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. This is joint work with A. Abiad and A. Jabal.