Skip to main content
3 of 3
added 15 characters in body
Delio Mugnolo
  • 3.4k
  • 21
  • 42

largest adjacency eigenvalue of line graphs

It is well-known that the largest eigenvalue $\lambda_{\max}$ of the adjacency matrix of a graph $G$ lies between the average and the maximal degree of $G$. Another known lower estimate is due to Dvo\v{r}ák and Mohar and says that $$\lambda_{\max}\ge\sqrt{\deg_{\max}}.$$ The reason for this is that $\lambda_{\max}$ is motononic wrt graph inclusion, so one could pick a vertex of maximal degree and all the incident edges and delete the rest of the graph; since this star has maximal adjacency eigenvalue $\sqrt{\deg_{\max}}$, we are done.

What about line graphs? My feeling is that this estimate cannot be sharp, since line graphs are claw-free. What is the "minimal induced subgraph" around a vertex of maximal degree in a line graph? Can the above estimate be improved?

BONUS QUESTION: Is there any interpretation for the associated eigenvector?

Delio Mugnolo
  • 3.4k
  • 21
  • 42