¿El gráfico de ruta tiene menos conectividad algebraica entre gráficos simples, sin señas, conectados?

Question

Deje $G = (V, E)$ ser simple, sin dirección, sin ponderar el gráfico de $n$ nodos (todos los usos de la palabra "gráfico" en esta pregunta se refieren sólo a los gráficos de estas propiedades). Definir su Laplaciano como $$\begin{equation} L(G) = D(G) - A(G), \end{equation}$$ donde $D(G)$ $A(G)$ son, respectivamente, el grado y las matrices de adyacencia asociada con $G$.

La segunda-más mínimo autovalor de a $L(G)$, a menudo denotado $\lambda_2(L(G))$ o, simplemente, $\lambda_2$ al $G$ es entendido, fue llamado su algebraica de conectividad por Fiedler en la obra seminal de $[1]$, lo que mostró que un gráfico de $G$ está conectado si y sólo si $\lambda_2 > 0$.

Para cualquier fija $n \in \mathbb{N}$, hay un número finito de gráficos en $n$ nodos (sin tener que preocuparse acerca de exactamente cuántos posible que los gráficos no lo son, este número es claramente delimitado anteriormente por $2^n$), y de igual manera, hay un número finito de conectado gráficos en $n$ nodos. Mi pregunta es la siguiente.

Que simple, sin dirección, sin ponderar, gráfica conectada en $n$ nodos minimiza la expresión algebraica de la conectividad entre todos los gráficos de este tipo en $n$ nodos?

Mi sospecha es que la respuesta a esta pregunta es el camino de la gráfica, el pensamiento no he sido capaz de confirmar esto. Es conocido (por ejemplo, de $[1]$) que el camino de la gráfica en la $n$ nodos algebraica de conectividad $\lambda_2 = 2\left(1 - \cos\frac{\pi}{n}\right)$, y he hecho un par de experimentos numéricos en la generación de gráficos y tratando de encontrar uno con un valor menor de $\lambda_2$, aunque todavía no he encontrado un gráfico para cualquier valor de $n$.

He mirado en Godsil y Royle, y aunque no era, obviamente, un montón sobre la conectividad de los gráficos, yo no podía encontrar la respuesta a esta pregunta. También he hecho algunas buscar en Google con los términos de búsqueda como "menos gráfica conectada" y "mínimo algebraica de la conectividad de los gráficos," pero que no terminó nada bien.

[1] M. Fiedler, "Algebraica de Conectividad de Gráficos" Checoslovaco Matemática Diario, 1973, vol. 23, no. 2, pp 298-305.

Answer 1

El hecho de que el camino de la gráfica de $P_n$ minimiza algebraica de conectividad entre todos conectados gráficos con $n$ vértices se sigue de la proposición 4.3 en Fiedler del papel.

Esta es la propuesta de los estados (entre otras cosas) que la expresión algebraica de la conectividad de un grafo $G$ al menos $2 e(G) (1-\cos(\pi/n))$ donde $e(G)$ es el borde de la conectividad de $G$, es decir, el número mínimo de aristas que deben ser removidos para desconectar el gráfico.

Este hecho es también dicho de forma más explícita (con una referencia a Fiedler) como la Proposición 1.12 en Belhaiza et al la Variable Barrio de Búsqueda para Extremal Gráficos. XI. Límites en las Algebraica de Conectividad.