1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Would you be able to provide a reference for the lower bound $\lambda_{\text{max}} \geq \sqrt{\deg_{\text{max}}$ please? $\endgroup$
    – gen
    Commented Sep 22, 2023 at 19:20
  • 1
    $\begingroup$ Sure: doi:10.1016/j.jctb.2010.07.006 $\endgroup$
    – Delio Mugnolo
    Commented Oct 10, 2023 at 22:10

1 Answer 1

Reset to default
2
$\begingroup$

The lower bound is less than $$\frac{\deg_{\max}}2+1$$ but not by much.

Here is (part of) a graph with an edge adjacent to $10$ others and (part of) the corresponding line graph.

enter image description here

The largest eigenvalue is $4+\sqrt{14} \approx 5.87$

If $\deg_{\max}=D$ is even then this equal split is the best for minimizing the maximum eigenvalue which turns out to be

$$ \frac{D}2+1-\frac{4}{D+6} \lt \frac{D-2+\sqrt{D^2+12D+4}}2 \lt \frac{D}2+1$$

For odd $D$ the obvious split gives a similar but slightly higher lower bound.

The corresponding eigenvalue (normalized) gives the usual thing: the limiting distribution for location with a random walk.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Delio Mugnolo
    Commented Feb 16, 2017 at 9:23
  • $\begingroup$ 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. $\endgroup$
    – Delio Mugnolo
    Commented Feb 16, 2017 at 9:28
  • $\begingroup$ 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. $\endgroup$
    – Delio Mugnolo
    Commented Feb 16, 2017 at 9:50
  • 1
    $\begingroup$ @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. $\endgroup$
    – Aaron Meyerowitz
    Commented Feb 16, 2017 at 10:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .