Please use this identifier to cite or link to this item: https://doi.org/10.1006/ffta.2001.0341
Title: Highly symmetric expanders
Authors: Chee, Y.M.
Ling, S. 
Issue Date: Jul-2002
Citation: Chee, Y.M., Ling, S. (2002-07). Highly symmetric expanders. Finite Fields and their Applications 8 (3) : 294-310. ScholarBank@NUS Repository. https://doi.org/10.1006/ffta.2001.0341
Abstract: Expander graphs are relevant to theoretical computer science in addition to the construction of high-performance switching networks. In communication network applications, a high degree of symmetry in the underlying topology is often advantageous, as it may reduce the complexity of designing and analyzing switching and routing algorithms. We give explicit constructions of expander graphs that are highly symmetric. In particular, we construct infinite families of Ramanujan graphs with large guarantees on the orders of their automorphism groups. Although nonlinear, our expander graphs are within a constant factor of the size of the smallest graphs exhibiting the same expansion properties. This work generalizes and extends in several directions a previous explicit construction of expander graphs based on finite projective spaces due to Alon. © 2002 Elsevier Science (USA).
Source Title: Finite Fields and their Applications
URI: http://scholarbank.nus.edu.sg/handle/10635/103373
ISSN: 10715797
DOI: 10.1006/ffta.2001.0341
Appears in Collections:Staff Publications

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

Page view(s)

31
checked on Aug 3, 2018

Google ScholarTM

Check

Altmetric


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