Conectividade algébrica

O icosaedro truncado, visto como um grafo, possui conectividade de vértices 3, porém conectividade algébrica de 0,243.

A conectividade algébrica de um grafo é o segundo menor autovalor da sua matriz Laplaciana associada.[1] Fiedler mostrou[2] que um grafo é conexo se, e somente se, o seu segundo menor autovalor Laplaciano é positivo. Denotamos a conectividade algébrica por a(G).

Relação com outros Parâmetros

Se o número de vértices de um grafo conexo é n e D é o diâmetro, a conectividade algébrica é limitada inferiormente por 4/nD.[3]

As conectividades algébrica, de vértices e de arestas, respectivamente a(G), κ(G) e λ(G), estão relacionadas de acordo com o resultado abaixo, provado por Fiedler.

Teorema

Se G não é um grafo completo então a(G) ≤ κ(G) ≤ λ(G).

Ao contrário da conectividade tradicional, a conectividade algébrica é dependente do número de vértices, bem como a maneira pela qual os vértices estão ligados. Nos grafos aleatórios, a conectividade algébrica diminui com o número de vértices, e aumenta com o grau médio. [4]

A conectividade algébrica também se relaciona com outras propriedades de conectividade, tais como o número isoperimétrico, que é limitado inferiormente por metade da conectividade algébrica.

Referências

1. Weisstein, Eric W. Algebraic Connectivity. From MathWorld--A Wolfram Web Resource.
2. Algebraic connectivity of graphs, by Miroslav Fiedler, Czechoslo- vak Mathematical Journal, Vol. 23 (1973), 298-305.
3. Bojan Mohar, The Laplacian Spectrum of Graphs, in Graph Theory, Combinatorics, and Applications, Vol. 2, Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, Wiley, 1991, pp. 871–898.
4. Synchronization and Connectivity of Discrete Complex Systems, Michael Holroyd, International Conference on Complex Systems, 2006.

Ver também

• Portal da matemática