Propriedades espectrais de um grafo

AUTOR(ES)

Fritscher, Eliseu

DATA DE PUBLICAÇÃO

2011

RESUMO

Associadas a um grafo G, temos a matriz de adjacência A(G) e a matriz laplaciana L(G). Este trabalho descreve algumas propriedades dessas matrizes e de seus autovalores em relação a características estruturais do grafo. Veremos que, em geral, somente o espectro de G, isto é, conjunto de autovalores de A(G), não é capaz de revelar todas as informações a respeito do grafo. Apresentaremos também uma nova cota superior para a soma dos k maiores autovalores laplacianos de uma árvore com n vértices, para k {1, . . . , ng}. Esse limite nos permitirá demonstrar que, dentre todas as árvores de n vértices, a árvore com energia laplaciana máxima é a estrela Sn, o que foi conjecturado por Radenkovi¢ e Gutman [18].

ASSUNTO(S)

grafos teoria espectral polinomios matrizes

Documentos Relacionados

• Um algoritmo de planos-de-corte para o número cromático fracionário de um grafo
• Sobre o vetor de Fiedler e as componentes de Perron de um grafo
• Um tutorial sobre métodos pseudo-espectrais para controle ótimo computacional
• O grafo do ato analítico
• Propriedades espectrais da matéria orgânica leve-livre e leve intra-agregado de dois latossolos sob plantio direto e preparo convencional