< Terug naar vorige pagina


Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

Tijdschriftbijdrage - Tijdschriftartikel

The kth power of a graph G=(V,E), Gk, is the graph whose vertex set is V and in which two distinct vertices are adjacent if and only if their distance in G is at most k. This article proves various eigenvalue bounds for the independence number and chromatic number of Gk which purely depend on the spectrum of G, together with a method to optimize them. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well.

Tijdschrift: Discrete Mathematics
ISSN: 0012-365X
Issue: 3
Volume: 345
Jaar van publicatie:2022