5 votos

¡Radio espectral del gráfico "casi" normal?!

La respuesta a esta pregunta podría ser trivial.

El Gráfico Deje $G$ gráfico formado de dos $d$-regular los componentes conectados. Es decir, $G= H_1\cup H_2$ donde $H_1$, e $H_2$ $d$- regular y discontinuo. Deje $x\in H_1$$y\in H_2$. Deje $G'= G+xy$, $G'$ está conectado gráfico. Mi pregunta es:

Pregunta: ¿Cuál es el mayor autovalor positivo de $G'$ ? O $\lambda_1 (G') = ??$

Ideas:

-Es obvio que $\lambda_1 (G) = d$ con multiplicidad 2 ( ya que está formado de 2 $d$-regular los componentes conectados). Pero no tengo idea de cómo calcular los $\lambda_1$ cuando de un solo filo se añade entre $H_1$, e $H_2$.

-El entrelazado teorema podría ayudar en commutating obligado para el máximo autovalor.

Cualquier idea será útil!

2voto

Ken Puntos 106

En su caso, el entrelazado resultado que usted ha mencionado es que el $\lambda_1(G') \geq \lambda_2(G)=d$. En el otro sentido, Weyl de la desigualdad (el triángulo de la desigualdad de la espectral de la radio) le dice a usted $$\lambda_1(G') \leq \lambda_1(G) + \lambda_1(G-G')=d+1,$$ pero creo que podemos decir algo más fuerte.

Supongamos que tenemos $$A'v = \lambda v $$ donde $A'$ es la matriz de adyacencia de $G'$. Asumir WLOG que $|v(x)| \geq |v(y)|$, y deje $z$ ser un vértice tener la máxima $|v(z)|$ entre todos los vértices distintos de $x$$y$. Con el triángulo de la desigualdad y el autovalor definición, tenemos $$\lambda |v(x)| = |(A' v) x | \leq \sum_{w \sim x} |v(w)| \leq |v(x)| + d |v(z)|$$ (el $d$ vecinos de $x$ $H_1$ cada contribuir en la mayoría de las $|v(z)|$, e $y$ contribuye en la mayoría de las $|v(x)|$). Del mismo modo, $$\lambda |v(z)| = |(A' v) z| \leq \sum_{w \sim z} |v(w)| \leq |v(x)| + (d-1) |v(z)|$$

Deje $v'=\left(\begin{array}{c} |v(x)| \\ |v(z)| \end{array}\right)$, y deje $M=\left(\begin{array}{cc} 1 & d \\ 1 & d-1\end{array}\right)$. Las anteriores desigualdades nos dicen $$0 \leq \lambda v' \leq M v'$$ en cada coordenada, por lo que tenemos $$\lambda ||v'|| \leq ||M v'|| \leq ||M|| ||v'|| = \frac{1}{2} (d+\sqrt{d^2+4}) ||v'||$$ De modo que el radio espectral de $G'$ es en la mayoría de las $\frac{1}{2} (d+\sqrt{d^2+4})$. Para un gran $d$ esto es aproximadamente el $d+\frac{1}{d}$.

Tengo la sensación de que esto puede ser bien conocidas y clásicas, pero no tienen una referencia.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X