Limites nos autovalores menores da matriz de adjacência de um gráfico

8

Existe algum limite conhecido (não trivial) (de natureza combinatória, com base nas propriedades computáveis ​​em tempo poligímico de um gráfico) no terceiro, até o menor valor próprio de uma matriz de adjacência (não ponderada)? Por exemplo, sabemos que o maior valor próprio admite os seguintes limites Algo do sabor acima para , ? (Dado que isso pode ser negativo, o limite (inferior) pode parecer mais atraente.)

max(dmax,dave)λmax=λ1dmax
λii3|λi|
Dimitris
fonte

Respostas:

7

Você pode gostar deste artigo recente: http://arxiv.org/abs/1211.0589v1

O artigo mostra, por exemplo, que " para qualquer gráfico finito com vértices e todos , o maior valor própriok 2 knk2k " do Laplaciano do gráfico, ou seja, , " é no máximo ", onde é a matriz de adjacência e um limite no grau.L=IA/d1Ω(k3n3)Ad

Martin Schwarz
fonte