Tags: #definition

regular graph

A graph $G$ is regular if the degrees of all vertices are the same. We say that a graph is d-regular if every vertex has degree $d$.

Properties

• If $G$ is $d$-regular, $L$ is its Laplacian (Kirchoff) matrix, $A$ is its adjacency matrix, then $L=d{I}_n-A$ so the eigenvalues of $L$ are ${\lambda }_i=d-{\alpha }_i$ (where ${\alpha }_i$ are the spectrum of $G$, or the eigenvalues of $A$)
• The number of spanning trees on a $d$-regular graph $G$ is $\frac{1}{n}\cdot \prod _{i=1}^n(d-{\alpha }_i)$ (as a consequence of Kirchoff's matrix tree theorem)