Nonexistence of a circulant expander family

Abstract

The expansion constant of a simple graph G of order n is defined as h(G) = min0 ∈ for some fixed ∈ > 0. Existence of such families is known in the literature, but explicit construction is nontrivial. A folklore theorem states that there is no expander family of circulant graphs only. In this note, we provide an elementary proof of this fact by first estimating the second largest eigenvalue of a circulant graph, and then employing Cheeger's inequalities d-λ2(G)/2 ≤ h(G) ≤ √2d(d - λ2(G)) where G is a d-regular graph and λ2(G) denotes the second largest eigenvalue of G. Moreover, the associated equality cases are discussed. © Copyright Australian Mathematical Publishing Association Inc. 2010.