Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Eigenvalues of a completely disconnected graph

  1. Dec 28, 2011 #1
    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. jcsd
  3. Dec 28, 2011 #2

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  4. Dec 28, 2011 #3
    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
  5. Dec 28, 2011 #4

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  6. Dec 28, 2011 #5
    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
  7. Dec 28, 2011 #6

    I like Serena

    User Avatar
    Homework Helper

    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
  8. Dec 28, 2011 #7
    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:

  9. Dec 28, 2011 #8
    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!!
     
  10. Dec 28, 2011 #9

    I like Serena

    User Avatar
    Homework Helper

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Eigenvalues of a completely disconnected graph
  1. Completely Lost (Replies: 10)

  2. Completeness relations (Replies: 4)

Loading...