Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Both the signed ($D-A$) and unsigned ($D+A$) Laplacian are of interest in spectral graph theory, see eg Cvetkovic: Bibliography on the signless Laplacian eigenvalues: first one hundred references.

Considering the spectral function $D+\rho A$ over the interval $\rho \in [-1,1]$ rather than just the extreme values $\rho={-1,1}$, results in the curves $\lambda_i(\rho)$.

For example, the following fractional spectra are are shown as point interpolations (as opposed to curve following, as in bifurcation theory) corresponding to some random Bernoulli graphs with increasing connectivity:

enter image description here

enter image description here

enter image description here

enter image description here enter image description here

These experimental results raise basic questions:

  • If graphs are $M$-cospectral on $\rho = {-1,1}$ are they cospectral for $\rho \in [-1,1]$?

  • Are there no intersections of $\lambda_i(\rho)$ outside $\rho \in [-1,1]$?

  • Does $\lim_{\lambda_i \to \infty}\frac{d\lambda_i}{d\rho} = const?$

  • What's the combinatorial interpretation of intersections in $\rho \in [-1,1]$?

Feel free to add your own conjectures.

share|improve this question

1 Answer 1

Let G0 be the graph with edge set $$ (0, 1), (0, 7), (0, 8), (1, 2), (2, 3), (2, 5), (2, 7), (2, 8), (3, 4), (3, 6), (4, 5), (5, 6), (6, 7) $$ and let G1 be the graph with edge set $$ (0, 1), (0, 3), (0, 5), (0, 8), (1, 2), (1, 4), (2, 3), (2, 8), (2, 9), (3, 4), (4, 5), (4, 8), (6, 7) $$ (Neither graph is connected and G0 has an isolated vertex.) The Laplacian matrices of these two graphs are cospectral. As these graphs are bipartite, their signless Laplacians are also cospectral. However the respective degree sequences are $$ [0, 2, 2, 2, 3, 3, 3, 3, 3, 5], [1, 1, 1, 2, 3, 3, 3, 4, 4, 4] $$ and so the answer to your first question is no.

share|improve this answer
    
Chris, thanks for that. Curious how you discovered this, or is it a well known counterexample? ... I will visually compare the fractional spectra when I get a chance. –  alancalvitti May 21 '13 at 21:08
    
@alancalvitti: If your conjecture was correct, Laplacian cospectral bipartite graphs would have to have the same degree sequence. But I was fairly sure that was false, and so I used sage to work through the small Laplacian cospectral bipartite graphs. (Feel free to email me about this stuff.) –  Chris Godsil May 21 '13 at 22:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.