On the sizes of expander graphs and minimum distances of graph codes

Tom Høholdt, Jørn Justesen

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

We give lower bounds for the minimum distances of graph codes based on expander graphs. The bounds depend only on the second eigenvalue of the graph and the parameters of the component codes. We also give an upper bound on the size of a degree regular graph with given second eigenvalue.
Original languageEnglish
JournalDiscrete Mathematics
Volume325
Pages (from-to)38-46
ISSN0012-365X
DOIs
Publication statusPublished - 2014

Keywords

  • Graph codes
  • Minimum distance
  • Eigenvalue

Cite this