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

Tom Høholdt; Jørn Justesen

doi:10.1016/j.disc.2014.02.005

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

Tom Høholdt
, Jørn Justesen

Research output: Contribution to journal › Journal article › Research › peer-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 language	English
Journal	Discrete Mathematics
Volume	325
Pages (from-to)	38-46
ISSN	0012-365X
DOIs	https://doi.org/10.1016/j.disc.2014.02.005
Publication status	Published - 2014

Keywords

Graph codes
Minimum distance
Eigenvalue

Access to Document

10.1016/j.disc.2014.02.005

OpenUrl availability

Check availability in DTU Findit

Cite this

@article{a9128424807c4db1b3cb6de5f2bc68fa,

title = "On the sizes of expander graphs and minimum distances of graph codes",

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.",

keywords = "Graph codes, Minimum distance, Eigenvalue",

author = "Tom H{\o}holdt and J{\o}rn Justesen",

year = "2014",

doi = "10.1016/j.disc.2014.02.005",

language = "English",

volume = "325",

pages = "38--46",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Høholdt, Tom

AU - Justesen, Jørn

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Graph codes

KW - Minimum distance

KW - Eigenvalue

U2 - 10.1016/j.disc.2014.02.005

DO - 10.1016/j.disc.2014.02.005

M3 - Journal article

SN - 0012-365X

VL - 325

SP - 38

EP - 46

JO - Discrete Mathematics

JF - Discrete Mathematics

ER -

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

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this