Name
Title | ||
|---|---|---|
Optimization of eigenvalue bounds for the independence and chromatic number of graph powers |
Abstract | ||
|---|---|---|
The kth power of a graph G = (V, E), G(k), 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 G(k) 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. (C) 2021 Published by Elsevier B.V. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.disc.2021.112706 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
k-power graph, Independence number, Chromatic number, Eigenvalue interlacing, k-partially walk-regular, Integer programming | Journal | 345 |
Issue | ISSN | Citations |
3 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aida Abiad | 1 | 16 | 5.66 |
| Gabriel Coutinho | 2 | 6 | 5.23 |
| M. A. Fiol | 3 | 816 | 87.28 |
| Bruno Nogueira | 4 | 0 | 0.34 |
| Sjanne Zeijlemaker | 5 | 0 | 0.34 |