Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/74421| Tipo: | Artigo de Periódico |
| Título: | Optimization of eigenvalue bounds for the independence and chromatic number of graph powers |
| Título(s) alternativo(s): | Otimização de limites de autovalores para a independência e número cromático de potências gráficas |
| Autor(es): | Aida Abiad Gabriel de Morais Coutinho Miquel Àngel Fiol Bruno D. Nogueira Sjanne Zeijlemaker |
| Resumen: | 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. |
| 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. |
| Asunto: | Teoria dos Grafos Programação (Computadores) |
| Idioma: | eng |
| País: | Brasil |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Institución: | UFMG |
| Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
| Tipo de acceso: | Acesso Aberto |
| Identificador DOI: | https://doi.org/10.1016/j.disc.2021.112706 |
| URI: | http://hdl.handle.net/1843/74421 |
| Fecha del documento: | 2022 |
| metadata.dc.url.externa: | https://www.sciencedirect.com/science/article/pii/S0012365X21004192 |
| metadata.dc.relation.ispartof: | Discrete Mathematics |
| Aparece en las colecciones: | Artigo de Periódico |
archivos asociados a este elemento:
| archivo | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| Optimization of eigenvalue bounds.pdfA.pdf | 335.74 kB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.