CARACTERIZAÇÃO DE GRAFOS COM CONECTIVIDADE ALGÉBRICA MÁXIMA

Vol 54, 2022 - 152891
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Este trabalho é focado no estudo da maximização da conectividade algébrica a(G), definida como o segundo menor autovalor Laplaciano de um grafo G. Esse parâmetro tem uma boa relação com a conexidade do grafo, sendo alvo de inúmeros estudos em razão de sua alta aplicabilidade em novas tecnologias. Motivados por uma de suas aplicações, caracterizamos os grafos que maximizam essa invariante, dado o número de vértices n. Além do grafo completo, caracterizamos todos os grafos que atingem os maiores valores possíveis para a conectividade algébrica, tais que a(G)>n-4, exibindo sua expressão de formação. Por fim construímos uma família infinita de grafos cuja conectividade algébrica atinge a cota máxima dada pelo grau mínimo do grafo.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Instituto Federal de Educação, Ciência e Tecnologia do Sudeste de Minas Gerais
Eixo Temático
  • 19 - TAG – Teoria e Algoritmos em Grafos
Palavras-chave
Conectividade Algébrica
Maximização
Grau Mínimo