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.
