Paper Info
Title
Optimal Bipartite Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterizations and Applications to Expander/LDPC Codes
Abstract
We characterize optimal bipartite expander graphs and give necessary and sufficient conditions for optimality. We determine the expansion parameters of the BIBD graphs and show that they yield optimal expander graphs that are also bipartite Ramanujan graphs. In particular, we show that the bipartite graphs derived from finite projective and affine geometries yield optimal Ramanujan graphs. This in turn leads to a theoretical explanation of the good performance of a class of LDPC codes.
Year
DOI
Venue
2009
10.1007/978-3-642-02181-7_6
AAECC
Keywords
Field
DocType
finite projective,bipartite ramanujan graph,bibd graph,balanced incomplete block designs,ldpc codes,bipartite graph,optimal expander graph,optimal bipartite ramanujan graphs,ldpc code,affine geometries,expansion parameter,optimal bipartite expander graph,optimal ramanujan graph,expander graphs,bipartite graphs,balanced incomplete block design,expander graph
Discrete mathematics,Combinatorics,Indifference graph,Expander graph,Chordal graph,Expander code,Cograph,Mathematics,Maximal independent set,Strong perfect graph theorem,Dense graph
Conference
Volume
ISSN
Citations 
5527
0302-9743
3
PageRank 
References 
Authors
0.53
21
2
Name
Order
Citations
PageRank
Tom Høholdt118628.53
Heeralal Janwal230.53