Efeito de diferentes operações gráficas na conectividade algébrica do gráfico laplaciano?

A conectividade algébrica de um gráfico G é o segundo menor valor próprio da matriz laplaciana de G. Esse valor próprio é maior que 0 se e somente se G for um gráfico conectado. A magnitude desse valor reflete o quão bem conectado o gráfico geral está.

por exemplo, " adicionar auto-loops " não altera os autovalores laplacianos (especialmente a conectividade algébrica) do gráfico. Porque laplaciano (G) = DA é invariável em relação à adição de auto-loops.

Minha pergunta é:

Alguém estudou o efeito de diferentes operações (como a contração da borda) no espectro de laplaciano? você conhece boas referências?

Observação: a definição exata da conectividade algébrica depende do tipo de Laplaciano usado. Para esta pergunta, prefiro usar a definição de Fan Chung na TEORIA DO GRÁFICO ESPECTRAL . Neste livro, Fan Chung utilizou uma versão redimensionada do Laplaciano, eliminando a dependência do número de vértices.

Ajudaria se você fornecer alguma motivação e experiência. Por favor, consulte Como fazer uma boa pergunta? e as perguntas frequentes do site .

Kaveh

Também estou interessado no caso de contração de borda. Passei algum tempo tentando encontrar referências sobre a relação entre autovalores e operações menores, sem sucesso.

Hsien-Chih Chang # 16/11

Para mim, a motivação parece bastante clara.

Suresh Venkat

Eu segundo Suresh, sabendo como várias operações influenciam o Laplaciano é interessante por si só e esses problemas aparecem em vários contextos.

Marcin Kotowski

Respostas:

Operações intuitivas que preservam a conectividade não diminuirão os valores próprios. Por exemplo, adicionar arestas ao gráfico não diminui a conectividade.

Em geral, se H é um subgráfico de um gráfico G, entrelaçando, sabemos que o i-ésimo maior autovalor de Laplaciano de H não é maior que o i-ésimo maior autovalor de Laplacian de G. Uma prova pode ser encontrada na Proposição 3.2. 1 do livro " Spectra of graphs " de Brouwer e Haemers. Observe que a definição de Laplaciano usada no livro não é normalizada; possui graus de nó na diagonal e -1 (ou 0 se não houver aresta) nas entradas fora da diagonal.

Hsien-Chih Chang 張顯之
fonte

Obrigado Chang. Sua resposta é realmente útil para mim. Mas se usarmos a definição de Laplaciano que não é normalizada, muitas das comparações parecem não ter sentido. Por exemplo, temos conectividade algébrica (K10) = 10 e conectividade algébrica (K20) = 20. no entanto, ambos os gráficos são gráficos simples totalmente conectados. Mas se usarmos o Laplaciano normalizado, então NormalizedAlgebraicConnectivity (K10) = NormalizedAlgebraicConnectivity (K20) = 1 e, portanto, a comparação da versão normalizada parece ser mais racional e natural.

@behnam: Eu concordo com você. Mas após a normalização, algumas das propriedades não decrescentes podem diferir. (Say pode-se garantir um rigoroso diminuindo em maiores Laplaciano bordas quando exclusão para os não normalizadas, mas não para os normalizados.)

Hsien-Chih Chang張顯之

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{3})

$\Theta(n^3)$

@TysonWilliams Você está muito certo. Esse é um dos aspectos teóricos em que os laplacianos normalizados e não normalizados diferem. Ao adicionar arestas, a conectividade algébrica não normalizada sempre aumenta (Fiedler), mas há exemplos (nem muito complicados) que mostram que as arestas adicionadas nos lugares errados podem diminuir a conectividade. Isso é particularmente fácil de ver se você permite pesos na borda.

Delio M.