7
$\begingroup$

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.

1 Answers 1

3

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.

  • 0
    @alancalvitti: google will work2015-01-15