MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 Typo

I'd guess

I guessed no but Gordon has changed my mind for degree greater than 2.

If it has degree 2 it is a union of cycles. Eigenvalues are $2\cos(\frac{2 \pi j}{k})$ for various $k$. In particular 2 has multiplicity the number of components.

For random regular graphs of degree more than 2 I'd wildly guess that the eigenvalue behavior is like that of a large random symmetric matrix. This has been well studied, but not by me, all I know is the phrase "Gaussian Orthogonal Ensemble".

Some experiments with degree 3 graphs suggest that with 30 vertices one component is highly likely and there is a repeated eigenvalue ( most often 0) about 2% of the time. At 60 vertices it is more like 0.2%.

I'd guess no. If it has degree 2 it is a union of cycles. Eigenvalues are doubles of cosines of $\frac{2 2\cos(\frac{2 \pi j}{k}$ j}{k})$for various$ k$. In particular 2 has multiplicity the number of components. For random regular graphs of degree more than 2 I'd wildly guess that the eigenvalue behavior is like that of a large random symmetric matrix. This has been well studied, but not by me, all I know is the phrase "Gaussian Orthogonal Ensemble". 1 Id guess no. If it has degree 2 it is a union of cycles. Eigenvalues are doubles of cosines of$\frac{2 \pi j}{k}$for various$ k\$. In particular 2 has multiplicity the number of components.