Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
Carregando...
Data
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Artigo de periódico
Título alternativo
Otimização de limites de autovalores para a independência e número cromático de potências gráficas
Primeiro orientador
Membros da banca
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.
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.
Assunto
Teoria dos Grafos, Programação (Computadores)
Palavras-chave
Graph Theory, Computers - Programming
Citação
Departamento
Curso
Endereço externo
https://www.sciencedirect.com/science/article/pii/S0012365X21004192