Minimum Degree of Maximally Eigencentral Vertices

29 Views Asked by At

In Grassi et al. (2007), they state the following theorem:

Let $G(V,E)$ be a connected graph and $A$ its adjacency matrix, with spectral radius $\rho$ and principal eigenvector $x$. Let us consider the sets: $U=\{v\in V:x_v=\max_{i\in V}x_i\}$ and $W=\{w\in V:x_w=\min_{i\in V}x_i\}$ and let $d_{min}=\min\{d_v:v\in U\}$ and $d_{max}=\max\{d_w:w\in W\}$. Then $d_{max}\leq\rho\leq d_{min}$. One of the bounds holds as an equality if and only if $G$ is a regular graph; in this case both bounds actually hold as equalities.

So I interpreted the last statement to mean that if $d_{max}=\rho$, then $G$ must be a regular graph (or if $d_{min}=\rho$, then $G$ is a regular graph). But this statement is completely false; in fact Figure 2 in the paper, right before this theorem, gives a counterexample! (The counterexample is a binary tree of depth 3, and $d_{max}<\rho=d_{min}=2$) But I'm not sure what else it could mean. Any ideas on what they were trying to say?