Timeline for largest adjacency eigenvalue of line graphs
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 5, 2017 at 7:19 | vote | accept | Delio Mugnolo | ||
| Sep 5, 2017 at 7:19 | vote | accept | Delio Mugnolo | ||
| Sep 5, 2017 at 7:19 | |||||
| Feb 16, 2017 at 10:40 | comment | added | Aaron Meyerowitz | @DelioMugnolo It is possible to do the calculation for a less balanced split. For a heuristic note that this split gives the lowest average degree. The eigenvector for the largest eigenvalue is non-negative. Scale so that entries add to $1$ and you have a probability distribution. | |
| Feb 16, 2017 at 9:50 | comment | added | Delio Mugnolo | Btw, your lower bound is always larger than $D/2+5/9$ (except in the trivial cases where $D=1$ or $D=2$). Even this rough estimate returns something better than Mohar's $\sqrt{D}$. Nice. | |
| Feb 16, 2017 at 9:28 | comment | added | Delio Mugnolo | Concerning the correspondent eigenvector (I guess you actually mean this): your interpretation of course relies on renormalization, leading to huge differences between the adjacency matrix and its normalized version (aka transition matrix). Apart from this, what I'd like to see is a connecction with the topology of the graph: the smallest eigenvector of the Laplacian and signless Laplacian detect connected components and (almost) bipartite components, say, and the lowest eigenvector of the adjacency matrix of a line graph detects even cycles or couple of odd cycles in the pre-line graph. | |
| Feb 16, 2017 at 9:23 | comment | added | Delio Mugnolo | Thanks! The idea of taking an edge-based star is very natural indeed. However, I have difficulties understanding why a left/right equipartition is the worst case scenario. True, heuristics suggest that the largest eigenvalue is lower if the graph is "less bipartite", but still I don't see a formal reason. | |
| Feb 16, 2017 at 1:57 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |