$4$-Circulant Graphs

Abstract

A $4$-regular graph $G$ is called a $4$-circulant if its adjacency matrix $A(G)$ is a circulant matrix. Because of the special structure of the eigenvalues of $A(G)$, the rank of such graphs is completely determined. We show how all disconnected $4$-circulants are made up of connected $4$-circulants and classify all connected $4$-circulants as isomorphic to one of two basic types.