# Eigenvalues of a completely disconnected graph

1. Dec 28, 2011

### 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!!

2. Dec 28, 2011

### I like Serena

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.

3. Dec 28, 2011

### 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/ [Broken]

Last edited by a moderator: May 5, 2017
4. Dec 28, 2011

### I like Serena

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.

5. Dec 28, 2011

### kosmos

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

Last edited by a moderator: May 5, 2017
6. Dec 28, 2011

### I like Serena

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. :)

Last edited by a moderator: May 5, 2017
7. Dec 28, 2011

### 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

#### Attached Files:

• ###### data.txt
File size:
1.6 KB
Views:
66
8. Dec 28, 2011

### 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!!

9. Dec 28, 2011

Cheers!