Question about multiplicity of an eigenvalue for $d-$regular graph

409 Views Asked by At

Claim: Let $G$ be a $d-$regular graph. Then the multiplicity of the eigenvalue $\lambda=d$ is the number of components. Every eigenvector belonging to $d$ is constant on each component.

Proof: I got it from Prop $1.9$ in here. Let $x$ be an eigenvector corresponding to $d$. We show that it is constant on a connected component. Let $H$ be a connected component and let $c = \max_{i\in V(H)} x_i$. Let $V_c = \{i\in V(H)|x_i = c\}$ and $V(H)\setminus V_c = \{i\in V(H)|x_i < c\}$. If $V(H)\setminus V_c$ is not empty, then $\exists$ an edge $(i,j)\in E(H)$ s.t. $i\in V_c$ and $j\in V(H)\setminus V_c$. Then

$$dc = dx_i = \sum_{k\in N(i)}x_k\leq x_j + \sum_{k\in N(i),k\neq j}x_k<c+(d-1)c=dc$$

a contradiction. Thus $x$ is constant on each component.

Two questions:

1) Why does If $V(H)\setminus V_c$ is not empty imply $\exists$ an edge $(i,j)\in E(H)$ s.t. $i\in V_c$ and $j\in V(H)\setminus V_c$?

2) Why is $dx_i = \sum_{k\in N(i)}x_k$? This means $x_i$ is like a harmonic function and is an arithmetic average of $x_k'$s of its neighbors.

Thanks.

1

There are 1 best solutions below

0
On BEST ANSWER

1) $V_c$ is the subset of $V(H)$ with maximal entry among the vertices in $H$ in the eigenvector $x$, which is nonempty by definition. Suppose $V(H)\setminus V_c$ is nonempty. Then if there were no edge $(i,j)\in E(H)$ in $i\in V_c$ and $j\in V(H)\setminus V_c$, then $V(H)$ could be partitioned into two components with no edges between them, namely $V(H)\setminus V_c$ and $V_c$, which would violate $H$ being a connected component.

2) $dx_i=\sum_{k\in N(i)} x_k$ follows from the eigenvalue equation, as you supposed $d$ is the eigenvalue for $x$. Namely, this is the $i$th entry of the eigenvalue equation $Ax=dx$.