- This event has passed.

# CO seminar – Luuk Reijnders

## March 15 @ 12:30 - 13:30

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