Next: Bipartite graphs Up: The spectrum of a Previous: Automorphisms

Regular graphs

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

Proposition 1.7.1   Let be a graph with eigenvalues . Equivalent are:

1. is regular (of degree ),
2. ,
3. .

Proof:    We have seen that (i) and (ii) are equivalent. Also, if is regular of degree , then . Conversely, if (iii) holds, then and by the above is regular.

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

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

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

Both and have spectrum , , (where multiplicities are written as exponents). And both and have spectrum , , , , .

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

Proposition 1.7.3   The graph is regular and connected if and only if there exists a polynomial such that .

Proof:    If , then commutes with and hence is regular (and clearly also connected). Conversely, let be connected and regular. Choose a basis such that the commuting matrices and become diagonal. Then becomes and becomes . Hence, if we put , then , so that satisfies the requirements.

Next: Bipartite graphs Up: The spectrum of a Previous: Automorphisms
Andries Brouwer 2003-09-30