0
$\begingroup$

Consider a connected undirected graph $\Gamma$ with an adjacency matrix $A=(a_{ij})_{i,j}$ where $a_{ii}=0$ (and by definition $a_{ij} \in \{0,1\}$ and $a_{ij} = a_{ji}$). Let $\Delta(\Gamma)$ denote the maximum degree of the graph. If an eigenvalue $\lambda = -\Delta(\Gamma)$, we can show for the eigenvector $v=(v_1, \dots ,v_n)^T$ associated with $\lambda$ that $|v_1|=\dots=|v_n|$.

My question is: how do you prove that $\Gamma$ is regular, i.e. that there are the same number of $1$'s in each row/column of the adjacency matrix?

I tried to prove this using $Av=\lambda v$, but this only works for me if $v_1=\dots=v_n$.

$\endgroup$
  • $\begingroup$ Can you clarify the question? What are you assuming about your graph, and what do you want to prove about it? $\endgroup$ – Joppy Apr 5 '18 at 12:27
  • $\begingroup$ @Joppy I assume that there is an eigenvalue which is the opposite number of the maximum degree. I need to prove that the graph is regular if such an eigenvalue exists. $\endgroup$ – Sivlirpa Apr 5 '18 at 12:35
0
$\begingroup$

Normalize the eigenvector so that $|v_j|=1, 1\le j\le N.$ For each $j,$ $$\sum_{i=1}^{N}{a_{ij}v_j}=-\Delta(\Gamma)v_j\\ \Delta(\Gamma)=|-\Delta(\Gamma)v_j|=\left\lvert\sum_{i=1}^{N}{a_{ij}v_j}\right\rvert\le\sum_{i=1}^{N}{|a_{ij}|}=\sum_{i=1}^{N}{a_{ij}} \le \Delta(\Gamma), $$ where the last inequality is by definition of \Delta(\Gamma).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.