Please use this identifier to cite or link to this item: https://doi.org/10.1017/S0004972710001644
Title: Nonexistence of a circulant expander family
Authors: Leung, K.H. 
Nguyen, V.
So, W.
Keywords: Cheeger's inequality
circulant graph
expander family
Issue Date: Feb-2011
Citation: Leung, K.H., Nguyen, V., So, W. (2011-02). Nonexistence of a circulant expander family. Bulletin of the Australian Mathematical Society 83 (1) : 87-95. ScholarBank@NUS Repository. https://doi.org/10.1017/S0004972710001644
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.
Source Title: Bulletin of the Australian Mathematical Society
URI: http://scholarbank.nus.edu.sg/handle/10635/103612
ISSN: 00049727
DOI: 10.1017/S0004972710001644
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

34
checked on Dec 7, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.