Efecto de diferentes operaciones de grafo en la conectividad algebraica de grafo laplaciano?

La conectividad algebraica de un gráfico G es el segundo valor propio más pequeño de la matriz laplaciana de G. Este valor propio es mayor que 0 si y solo si G es un gráfico conectado. La magnitud de este valor refleja qué tan bien conectado está el gráfico general.

por ejemplo, " agregar bucles automáticos " no cambia los valores propios laplacianos (especialmente la conectividad algebraica) del gráfico. Porque, laplaciano (G) = DA es invariante con respecto a la adición de auto-bucles.

Mi pregunta es:

¿Alguien ha estudiado el efecto de diferentes operaciones (como la contracción del borde) en el espectro de laplaciano? conoces buenas referencias?

Observación: la definición exacta de la conectividad algebraica depende del tipo de laplaciano utilizado. Para esta pregunta, prefiero usar la definición de Fan Chung en SPECTRAL GRAPH THEORY . En este libro, Fan Chung ha puesto en práctica una versión reescalada del Laplaciano, eliminando la dependencia del número de vértices.

Sería de ayuda si proporciona alguna motivación y antecedentes. Por favor, vea ¿Cómo hacer una buena pregunta? y las preguntas frecuentes del sitio .

Kaveh

También estoy interesado en el caso de contracción del borde. He pasado algún tiempo tratando de encontrar referencias sobre la relación entre valores propios y operaciones menores, sin éxito.

Hsien-Chih Chang 張顯之

Para mí, la motivación parece bastante clara.

Suresh Venkat

Segundo Suresh, saber cómo varias operaciones influyen en el laplaciano es interesante en sí mismo y este problema aparece en varios contextos.

Marcin Kotowski

Respuestas:

Intuitivamente, las operaciones que preservan la conectividad no disminuirán los valores propios. Por ejemplo, agregar bordes al gráfico no disminuye la conectividad.

En general, si H es un subgrafo de un gráfico G, al entrelazar sabemos que el i-ésimo valor propio de Laplacian más grande de H no es mayor que el i-ésimo valor propio de Laplacian más grande de G. Una prueba se puede encontrar en la Proposición 3.2. 1 del libro " Spectra of graphs " de Brouwer y Haemers. Tenga en cuenta que la definición de laplaciano utilizada en el libro no está normalizada; tiene grados de nodo en la diagonal y -1 (o 0 si no hay borde) en las entradas fuera de la diagonal.

Hsien-Chih Chang 張顯之
fuente

Gracias Chang Tu respuesta es realmente útil para mí. Pero si usamos la definición de Laplaciano que no está normalizada, muchas de las comparaciones parecen no tener sentido. Por ejemplo, tenemos conectividad algebraica (K10) = 10 y conectividad algebraica (K20) = 20. sin embargo, ambos gráficos son gráficos simples totalmente conectados. Pero si usamos el Laplaciano normalizado, entonces NormalizedAlgebraicConnectivity (K10) = NormalizedAlgebraicConnectivity (K20) = 1 y, por lo tanto, la comparación de la versión normalizada parece ser más racional y natural.

@behnam: estoy de acuerdo contigo. Pero después de la normalización, algunas de las propiedades no decrecientes pueden diferir. (Digamos que uno puede asegurar una disminución estricta en el Laplaciano más grande al eliminar bordes para los no normalizados, pero no para los normalizados.)

Hsien-Chih Chang 張顯之

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{3})

$\Theta(n^3)$

@TysonWilliams Tienes mucha razón. Este es uno de los aspectos teóricos en los que los laplacianos normalizados y no normalizados difieren. Al agregar bordes, la conectividad algebraica no normalizada siempre aumenta (Fiedler), pero hay ejemplos (ni siquiera muy complicados) que muestran que los bordes agregados en los lugares incorrectos pueden disminuir la conectividad. Esto es particularmente fácil de ver si permite pesos de borde.

Delio M.