1. Repositório Institucional da UFMG
  2. Publicações Científicas e Culturais
  3. Artigo de Periódico
Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/74421
Full metadata record
DC FieldValueLanguage
dc.creatorAida Abiadpt_BR
dc.creatorGabriel de Morais Coutinhopt_BR
dc.creatorMiquel Àngel Fiolpt_BR
dc.creatorBruno D. Nogueirapt_BR
dc.creatorSjanne Zeijlemakerpt_BR
dc.date.accessioned2024-08-20T20:34:41Z-
dc.date.available2024-08-20T20:34:41Z-
dc.date.issued2022-
dc.citation.volume345pt_BR
dc.citation.issue3pt_BR
dc.citation.spage112706pt_BR
dc.identifier.doihttps://doi.org/10.1016/j.disc.2021.112706pt_BR
dc.identifier.issn0012365Xpt_BR
dc.identifier.urihttp://hdl.handle.net/1843/74421-
dc.description.abstractA 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.pt_BR
dc.description.resumoThe 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.pt_BR
dc.format.mimetypepdfpt_BR
dc.languageengpt_BR
dc.publisherUniversidade Federal de Minas Geraispt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃOpt_BR
dc.publisher.initialsUFMGpt_BR
dc.relation.ispartofDiscrete Mathematicspt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectGraph Theorypt_BR
dc.subjectComputers - Programmingpt_BR
dc.subject.otherTeoria dos Grafospt_BR
dc.subject.otherProgramação (Computadores)pt_BR
dc.titleOptimization of eigenvalue bounds for the independence and chromatic number of graph powerspt_BR
dc.title.alternativeOtimização de limites de autovalores para a independência e número cromático de potências gráficaspt_BR
dc.typeArtigo de Periódicopt_BR
dc.url.externahttps://www.sciencedirect.com/science/article/pii/S0012365X21004192pt_BR
Appears in Collections:Artigo de Periódico

Files in This Item:
File Description SizeFormat 
Optimization of eigenvalue bounds.pdfA.pdf335.74 kBAdobe PDFView/Open
Show simple item record


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.