Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/96423
Title: Highly symmetric expanders
Authors: Chee, Yeow Meng
Ling, San
Keywords: DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
Issue Date: 2002
Source: Chee, Y. M., & Ling, S. (2002). Highly Symmetric Expanders. Finite Fields and Their Applications, 8(3), 294-310.
Series/Report no.: Finite fields and their applications
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 in finite 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.
URI: https://hdl.handle.net/10356/96423
http://hdl.handle.net/10220/9865
ISSN: 1071-5797
DOI: http://dx.doi.org/10.1006/ffta.2001.0341
Rights: © 2002 Elsevier Science (USA). This is the author created version of a work that has been peer reviewed and accepted for publication by Finite Fields and Their Applications, Elsevier Science (USA). It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1006/ffta.2001.0341].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
30. Highly Symmetric Expanders.pdf4.01 MBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.