Timeline for When does graph Laplacian have eigenvalue -1?
Current License: CC BY-SA 3.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Oct 5, 2013 at 23:09 | vote | accept | passerby51 | ||
| Oct 5, 2013 at 17:29 | answer | added | Chris Godsil | timeline score: 7 | |
| Oct 5, 2013 at 15:06 | comment | added | passerby51 | let us continue this discussion in chat | |
| Oct 5, 2013 at 15:05 | comment | added | joro | I am not sure, I put the degree sequence on the diagonal, should I put the degree of the vertices on the diagonal? | |
| Oct 5, 2013 at 15:03 | comment | added | passerby51 | @joro, Are you sure? The computer says that the smallest eigenvalue is $-0.7953$ for you third example. | |
| Oct 5, 2013 at 14:56 | comment | added | passerby51 | @joro, you second example also is disconnected and has a bipartite component $\{2,3,5\}$. | |
| Oct 5, 2013 at 14:55 | comment | added | joro |
This one is connected and not bipartite: [(0, 3), (0, 5), (0, 6), (1, 4), (2, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]
|
|
| Oct 5, 2013 at 14:54 | history | edited | passerby51 | CC BY-SA 3.0 |
added 280 characters in body
|
| Oct 5, 2013 at 14:52 | comment | added | passerby51 | @joro, that is because the graph is disconnected, and it has a connected component which is bipartite (namely $(0,4)$). I should have mentioned that the graph is connected. | |
| Oct 5, 2013 at 14:51 | comment | added | joro | Or maybe this one: [(0, 4), (1, 5), (1, 6), (2, 5), (2, 6), (3, 5), (3, 6), (5, 6)], [(0, 4), (0, 6), (1, 4), (1, 6), (2, 5), (3, 5), (4, 6)] | |
| Oct 5, 2013 at 14:50 | comment | added | passerby51 | @suv....rit, I understand, no hard feeling :) | |
| Oct 5, 2013 at 14:47 | comment | added | Suvrit | @passerby51: which is why i put it in "..." marks ;-) --- just to alert readers to the non-standard usage in your question, because the other definitions linked to are vastly more prevalent. | |
| Oct 5, 2013 at 14:44 | comment | added | joro |
According to my implementation the graph with edges [(0, 4), (1, 5), (1, 6), (2, 5), (2, 6), (3, 5), (3, 6), (5, 6)] has eigenvalue -1 and is not bipartite, not sure if this is correct. the min degree is 1.
|
|
| Oct 5, 2013 at 14:41 | comment | added | passerby51 | @joro, in fact (for the $L$ defined above) they seem to have exactly one eigenvalue $1$ and one eigenvalue $-1$ with the rest of the eigenvalues being zero. | |
| Oct 5, 2013 at 14:38 | comment | added | passerby51 | @joro, with my definition, both should have an eigenvalue $-1$. | |
| Oct 5, 2013 at 14:37 | comment | added | joro | What are the eigenvalues of K_{2,2} and K_{3,3} with your definition to test my implementation? | |
| Oct 5, 2013 at 14:36 | review | Close votes | |||
| Oct 5, 2013 at 17:30 | |||||
| Oct 5, 2013 at 14:32 | history | edited | passerby51 | CC BY-SA 3.0 |
added 161 characters in body
|
| Oct 5, 2013 at 14:20 | history | edited | passerby51 | CC BY-SA 3.0 |
added 268 characters in body
|
| Oct 5, 2013 at 14:19 | comment | added | passerby51 | @ suv....rit, A definition can't be wrong (it can be nonstandard). I am defining the Laplacian the way I mentioned above. You can rename it to whatever you like if you don't like the name. By the way, the eigenvalues of $I - D^{-1/2} A D^{-1/2}$ and $D^{-1/2} A D^{-1/2}$ are very closely related (by an affine transform $x \mapsto -x+1$). You can reformulate my question in terms of that matrix. | |
| Oct 5, 2013 at 14:17 | comment | added | passerby51 | @joro, There are many definitions of the Laplacian. The one I have mentioned in my post is a bit non-standard. (It is related to the symmetric Laplacian sometimes defined as $I - D^{-1/2} A D^{-1/2}$.) For the Laplacian that I defined, I still think what I wrote is correct. | |
| Oct 5, 2013 at 14:17 | comment | added | Suvrit | The definition you are using of the graph laplacian is different / "wrong" --- it is either $D-A$, or the normalized version $I-D^{-1/2}AD^{-1/2}$. The Graph Laplacian is a well-known semidefinite matrix, whose smallest eigenvalue is $0$---so it can never have $-1$ as an eigenvalue. | |
| Oct 5, 2013 at 14:10 | comment | added | joro | According to sage $K_{2,2}$ has eigenvalues of the Laplacian: [4, 0, 2, 2] and $K_{3,3}$: [6, 0, 3, 3, 3, 3] | |
| Oct 5, 2013 at 13:47 | history | asked | passerby51 | CC BY-SA 3.0 |