\(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.