On the k-independence number of graphs
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
No número de gráficos com independência k
Primeiro orientador
Membros da banca
Resumo
This paper generalizes and unifies the existing spectral bounds on the k-independence
number of a graph, which is the maximum size of a set of vertices at pairwise distance
greater than k. The previous bounds known in the literature follow as a corollary of the
main results in this work. We show that for most cases our bounds outperform the previous
known bounds. Some infinite families of graphs where the bounds are tight are also
presented. Finally, as a byproduct, we derive some spectral lower bounds for the diameter
of a graph.
Abstract
Este artigo generaliza e unifica os limites espectrais existentes na independência k
número de um gráfico, que é o tamanho máximo de um conjunto de vértices a uma distância entre pares
maior que k. Os limites anteriores conhecidos na literatura seguem como um corolário do
principais resultados neste trabalho. Mostramos que, na maioria dos casos, nossos limites superam os anteriores
limites conhecidos. Algumas famílias infinitas de gráficos onde os limites são estreitos também são
apresentado. Finalmente, como subproduto, derivamos alguns limites inferiores espectrais para o diâmetro
de um gráfico.
Assunto
Álgebra Linear, Teoria dos Grafos
Palavras-chave
Algebras, Linear, Graph Theory
Citação
Departamento
Curso
Endereço externo
https://www.sciencedirect.com/science/article/pii/S0012365X19300275