Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
| dc.creator | Aida Abiad | |
| dc.creator | Gabriel de Morais Coutinho | |
| dc.creator | Miquel Àngel Fiol | |
| dc.creator | Bruno D. Nogueira | |
| dc.creator | Sjanne Zeijlemaker | |
| dc.date.accessioned | 2024-08-20T20:34:41Z | |
| dc.date.accessioned | 2025-09-09T01:32:54Z | |
| dc.date.available | 2024-08-20T20:34:41Z | |
| dc.date.issued | 2022 | |
| dc.description.abstract | A k-ésima potência de um grafo G = (V , E), Gk, é o grafo cujo conjunto de vértices é V e no qual dois vértices distintos são adjacentes se e somente se sua distância em G for no máximo k. Este artigo prova vários limites de autovalor para o número de independência e número cromático de Gk que dependem puramente do espectro de G, juntamente com um método para otimizá-los. Nossos limites para o número de independência k também funcionam para sua contraparte quântica, que não é conhecido por ser um parâmetro computável em geral, justificando assim o uso de números inteiros programação para otimizá-los. Alguns dos limites previamente conhecidos na literatura segue como corolário de nossos principais resultados. Famílias infinitas de gráficos onde os limites são afiados também são apresentados. | |
| dc.format.mimetype | ||
| dc.identifier.doi | https://doi.org/10.1016/j.disc.2021.112706 | |
| dc.identifier.issn | 0012365X | |
| dc.identifier.uri | https://hdl.handle.net/1843/74421 | |
| dc.language | eng | |
| dc.publisher | Universidade Federal de Minas Gerais | |
| dc.relation.ispartof | Discrete Mathematics | |
| dc.rights | Acesso Aberto | |
| dc.subject | Teoria dos Grafos | |
| dc.subject | Programação (Computadores) | |
| dc.subject.other | Graph Theory | |
| dc.subject.other | Computers - Programming | |
| dc.title | Optimization of eigenvalue bounds for the independence and chromatic number of graph powers | |
| dc.title.alternative | Otimização de limites de autovalores para a independência e número cromático de potências gráficas | |
| dc.type | Artigo de periódico | |
| local.citation.issue | 3 | |
| local.citation.spage | 112706 | |
| local.citation.volume | 345 | |
| local.description.resumo | 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. | |
| local.publisher.country | Brasil | |
| local.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | |
| local.publisher.initials | UFMG | |
| local.url.externa | https://www.sciencedirect.com/science/article/pii/S0012365X21004192 |