Eigenvalues of a completely disconnected graph

[kosmos]

According to theory the eigenvalues of a completely disconnected graph (no two nodes are connected) must be all 0. But the normalized Laplacian of such a graph will be an identity matrix whose eigenvalues will be all 1s. Please correct me!!

[I like Serena]

According to theory the eigenvalues of a completely disconnected graph (no two nodes are connected) must be all 0. But the normalized Laplacian of such a graph will be an identity matrix whose eigenvalues will be all 1s. Please correct me!!

I believe you can not create a normalize Laplacian from a graph with isolated vertices.
They have degree 0, so you cannot calculate the entries $-1 \over \sqrt{d_i d_j}$ in the matrix.

[kosmos]

The value is 0 if the degree is 0 as per definition. So we will get an identity matrix.

http://www.math.ucsd.edu/~sbutler/spectral/

[I like Serena]

Can't find the reference in your link...

However, from wikipedia I can see that the entries on the main diagonal would be set to zero, so it will not be an identity matrix.
These entries would correspond to eigenvalues of zero.

[kosmos]

Page no. 9 of this pdf file http://www.math.ucsd.edu/~sbutler/PDF/spectral1.pdf .... and i think this reference has missed that out!! ....thanks for helping out mate!

[I like Serena]

Page no. 9 of this pdf file http://www.math.ucsd.edu/~sbutler/PDF/spectral1.pdf .... and i think this reference has missed that out!! ....thanks for helping out mate!

Yes, this reference missed out on that.
However, in the introductory paragraph it is assumed that there are no isolated vertices, so it is not wrong.

And you're welcome. :)

[kosmos]

I get the following eigenvalues for the matrix attached as text file. It can be viewed in spreadsheet as it is in csv format. The first eigen value is supposed to be zero. There are 20 nodes in graph. There are 3 pairs of nodes which are connected only to each other. So there are 15 partitions as shown by the values below, assuming -4 is zero.
-4.0
-2.220446049250313E-16
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
1.1102230246251565E-16
4.440892098500626E-16
1.9999999999999998
2.0
2.0
2.0
2.000000000000001

[kosmos]

Sorry for posting it in this thread ... I should have done it in the other one. I got the problem. The portion of my implementation which checked if the nodes where adjacent had a mistake. So it was producing wrong first eigenvalue. Now it works fine. I am getting the required number of zeroes and no negative values. :) ..... Thanks for your help again!!

[I like Serena]

Cheers! :smile: