Regular graphs

It is possible to see from the spectrum whether a graph is regular:

Proposition 1.7.1   Let $\Gamma$ be a graph with eigenvalues $k = \theta_1 \ge \theta_2 \ge ... \ge \theta_v$. Equivalent are:

1. $\Gamma$ is regular (of degree $k$),
2. $AJ = kJ$,
3. $\sum \theta_i^2 = kv$.

Proof:    We have seen that (i) and (ii) are equivalent. Also, if $\Gamma$ is regular of degree $k$, then $\sum \theta_i^2 = {\rm tr}A^2 = kv$. Conversely, if (iii) holds, then $\bar{k} = v^{-1} \sum \theta_i^2 = \theta_1$ and by the above $\Gamma$ is regular. $\Box$

It is also possible to see from the spectrum whether a graph is regular and connected:

Proposition 1.7.2   Let $\Gamma$ be regular of degree $k$. Then $k$ is an eigenvalue of $\Gamma$, and its multiplicity equals the number of connected components of $\Gamma$. In particular, $k$ is a simple eigenvalue if and only if $\Gamma$ is connected. $\Box$

But one cannot see from the spectrum alone whether a graph is connected:

Both $K_{1,4}$ and $K_1 + C_4$ have spectrum $2^1$, $0^3$, $(-2)^1$ (where multiplicities are written as exponents). And both $\hat{E}_6$ and $K_1 + C_6$ have spectrum $2^1$, $1^2$, $0$, $(-1)^2$, $(-2)^1$.

$$\begin{picture}(360,60)(-15,-5) \put(0,0){\circle{2}}\put(0.7... ...put(300,-8){\makebox(0,0)[c]{\small $K_1 + C_6$}} \end{picture}$$

Another very useful characterization of regular connected graphs was given by Hoffman [18]:

Proposition 1.7.3   The graph $\Gamma$ is regular and connected if and only if there exists a polynomial $p$ such that $J = p(A)$.

Proof:    If $J = p(A)$, then $J$ commutes with $A$ and hence $\Gamma$ is regular (and clearly also connected). Conversely, let $\Gamma$ be connected and regular. Choose a basis such that the commuting matrices $A$ and $J$ become diagonal. Then $J$ becomes ${\rm diag}( v , 0 , ... , 0 )$ and $A$ becomes ${\rm diag}( k , \theta_2 , ... , \theta_v )$. Hence, if we put $f(x) = \prod_{i=2}^v (x - \theta_i )$, then $J = vf(A)/f(k)$, so that $p(x) = vf(x)/f(k)$ satisfies the requirements. $\Box$