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

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 (\sqrt{d_{max}}, d_{ave}) \leq λ_{max} = λ_{1} \leq d_{max}

$\max(\sqrt{d_{\max}}, d_{\text{ave}})\le \lambda_{\max}=\lambda_1 \le d_{\max}$

λ_{i}

$\lambda_i$

i \geq 3

$i\ge 3$

| λ_{i} |

$|\lambda_i|$

graph-theory co.combinatorics spectral-graph-theory Dimitris
fonte

Respostas:

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óprio $n$ $k ≥ 2$ $k$ " do Laplaciano do gráfico, ou seja, , " é no máximo ", onde é a matriz de adjacência e um limite no grau. $L=I-A/d$ $1−\Omega(\frac{k^3}{n^3})$ $A$ $d$

Martin Schwarz
fonte