3
$\begingroup$

This is exercise 1.1.24 in "Graph Theory" by Bondy and Murty:

$(a)$ No eigenvalue of a Graph $G$ has absolute value greater than $\Delta$
$(b)$ If $G$ is a connected graph and $\Delta$ is an eigenvalue of $G$, then $G$ is regular
$(c)$ If $G$ is a connected graph and $-\Delta$ is an eigenvalue of $G$, then $G$ is regular and bipartite

I think I have managed to proof $(a)$, but would like somebody to confirm: (Note that $\Delta$ is the maximum degree and I write $d(x_i)$ for the degree of the vertex $x_i$.

Let $\lambda$ be some eigenvalue of $A$ with eigenvector $v \neq 0$. Choose $j$ such that $| v_j |$ is maximal among all $| v_i |$.
Evaluating $Av = \lambda v$ at $j$ we get $\sum\limits_{i \neq j}a_{ij}v_i=\lambda v_j$ and thus $$| \lambda | = \frac{| \sum\limits_{i \neq j}a_{ij}v_i |}{| v_j |} \leq \frac{ \sum\limits_{i \neq j}a_{ij}|v_i |}{| v_j |} \leq \frac{ \sum\limits_{i \neq j}a_{ij}|v_j |}{| v_j |} = \sum\limits_{i \neq j}a_{ij} = d(x_j) \leq \Delta$$

I am not sure how to tackle $(b)$ and $(c)$. I do know that to show regularity it is necessary and sufficient that $\Delta$ is an eigenvalue of $A$ with eigenvector $(1,\ldots,1)$, but I don't see how $G$ being connected helps me... Any hint or partial solution for either $(b)$ or $(c)$ would be much appreciated.

$\endgroup$
2
  • $\begingroup$ Alright so I have found out that $(a)$ is a special case of a theorem called Gershgorin circle theorem, and the proof of the theorem on wikipedia is essentially identical to the one I found. So I am almost certain it is fine. Still stuck with $(b)$ and $(c)$ though. $\endgroup$ Commented Jul 6, 2023 at 16:56
  • $\begingroup$ all three of these are standard results from Perron-Frobenius theory. It might be easiest to prove (b) under the original stricter Perron theory where $A$ is a positive matrix; Perron-Frobenius theory then generalizes this to the case of a non-negative matrix with a single communicating class which should be equivalent to G being connected. $\endgroup$ Commented Jul 6, 2023 at 19:03

1 Answer 1

2
$\begingroup$

We could prove $(b)$ and $(c)$ by your inequality chain.

$(b)$ If $G$ is a connected graph and $\Delta$ is an eigenvalue of $G$, then $G$ is regular.

Proof: Let $\lambda=\Delta$ be an eigenvalue of $A$ with eigenvector $v \neq 0$. Choose $j$ such that $| v_j |$ is maximal among all $| v_i |$.
Evaluating $Av = \lambda v$ at $j$ we get $\sum\limits_{i}a_{ij}v_i=\lambda v_j$ and thus \begin{equation} \Delta=\lvert\lambda\rvert = \frac{\Big\lvert\sum\limits_{i}a_{ij}v_i\Big\rvert}{| v_j |} \leq \frac{ \sum\limits_{i}a_{ij}|v_i|}{| v_j |} \leq \frac{ \sum\limits_{i}a_{ij}|v_j |}{| v_j |} = \sum_{i}a_{ij} = d(x_j) \leq \Delta\,.\tag{1}\label{eq:main} \end{equation}

The inequation \eqref{eq:main} becomes an equation exactly when $v_i$'s, whose corresponding $a_{ij}\ne 0$, have same sign due to the first inequality, and $\lvert v_i\rvert$'s must equal $\lvert v_j\rvert$ due to the second inequality. Furthermore, such $v_i$'s and $v_j$ have same sign since $\lambda=\Delta\ge 0$. As a result, $v_i$'s equal $v_j$.

We iteratively continue to consider another row, say, $i$th of $A$, where $v_i$ was determined before, with the same argument. On $i$th row, all eigenvector entries $v_k$'s where $a_{ik}\ne0$ equal $v_i$. Because $G$ is connected, we will entirely traverse all rows. (We can think of this step as Depth-first search or Bread-first search algorithms starting at the $j$th vertex.)

After all, we know that $(v_j,v_j,\ldots,v_j)$ is an eigenvector corresponding to the eigenvalue $\lambda=\Delta$, so does $(1,1,\ldots,1)$. Thus, the sum of each row of $A$ is $\Delta$, which means $G$ is regular.


We similarly prove $(c)$ (with a little bit complexity). We use the same notations in the previous proof, except that $\lambda=-\Delta$.

$(c)$ If $G$ is a connected graph and $-\Delta$ is an eigenvalue of $G$, then $G$ is regular and bipartite.

Proof: For the sake of equality of \eqref{eq:main}, $v_i$'s, whose corresponding $a_{ij}\ne 0$, have same sign due to the first inequality, and $\lvert v_i\rvert$'s must equal $\lvert v_j\rvert$ due to the second inequality. Furthermore, such $v_i$'s have opposite sign with $v_j$ since $\lambda=-\Delta\le0$. Thus, $v_i$'s equal $-v_j$. That implies $a_{jj}=0$ as well.

We iteratively continue to consider another row, say, $i$th of $A$, where $v_i$ was determined before, with the same argument. On $i$th row, all eigenvector entries $v_k$'s where $a_{ik}\ne0$ equal $-v_i$, and $a_{ii}=0$. Because $G$ is connected, we will entirely traverse all rows.

After all, getting an eigenvector whose entries are $v_j$ or $-v_j$, we scale it to one whose entries are $1$ or $-1$. If $v_i=v_k$, $i$th and $k$th vertices are not adjacent, so we partition vertices into 2 sides: one for $v_i=1$, one for $v_i=-1$. In addition, we can easily conclude that the sum of each row is $\Delta$. Consequently, G is bipartite and regular.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.