Eigenvalues and expansion of bipartite graphs

Tom Høholdt; Heeralal Janwa

doi:10.1007/s10623-011-9598-6

Eigenvalues and expansion of bipartite graphs

Tom Høholdt
, Heeralal Janwa

University of Puerto Rico

Research output: Contribution to journal › Journal article › Research › peer-review

3363 Downloads (Orbit)

Abstract

We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes that are optimal with respect to the bouns. We prove that BIBD-graphs are characterized by their eigenvalues. Finally we present a new bound on the expansion coefficient of (c,d)-regular bipartite graphs and compare that with aclassical bound.

Original language	English
Journal	Designs, Codes and Cryptography
Volume	65
Issue number	3
Pages (from-to)	259-273
ISSN	0925-1022
DOIs	https://doi.org/10.1007/s10623-011-9598-6
Publication status	Published - 2012

Keywords

Bipartite graphs
Expander graphs
Isoperimetric constant
Eigenvalues of graphs
Bipartite Ramanujan graphs
BIBD’s
Generalized N-gons
LDPC codes

Access to Document

10.1007/s10623-011-9598-6

DlibFinal published version, 128 KB

OpenUrl availability

Check availability in DTU Findit

Cite this

@article{83aaf7715fc64797b51ddf6f3b8b3255,

title = "Eigenvalues and expansion of bipartite graphs",

abstract = "We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes that are optimal with respect to the bouns. We prove that BIBD-graphs are characterized by their eigenvalues. Finally we present a new bound on the expansion coefficient of (c,d)-regular bipartite graphs and compare that with aclassical bound.",

keywords = "Bipartite graphs, Expander graphs, Isoperimetric constant, Eigenvalues of graphs, Bipartite Ramanujan graphs, BIBD{\textquoteright}s, Generalized N-gons, LDPC codes",

author = "Tom H{\o}holdt and Heeralal Janwa",

year = "2012",

doi = "10.1007/s10623-011-9598-6",

language = "English",

volume = "65",

pages = "259--273",

journal = "Designs, Codes and Cryptography",

issn = "0925-1022",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Eigenvalues and expansion of bipartite graphs

AU - Høholdt, Tom

AU - Janwa, Heeralal

PY - 2012

Y1 - 2012

N2 - We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes that are optimal with respect to the bouns. We prove that BIBD-graphs are characterized by their eigenvalues. Finally we present a new bound on the expansion coefficient of (c,d)-regular bipartite graphs and compare that with aclassical bound.

AB - We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes that are optimal with respect to the bouns. We prove that BIBD-graphs are characterized by their eigenvalues. Finally we present a new bound on the expansion coefficient of (c,d)-regular bipartite graphs and compare that with aclassical bound.

KW - Bipartite graphs

KW - Expander graphs

KW - Isoperimetric constant

KW - Eigenvalues of graphs

KW - Bipartite Ramanujan graphs

KW - BIBD’s

KW - Generalized N-gons

KW - LDPC codes

U2 - 10.1007/s10623-011-9598-6

DO - 10.1007/s10623-011-9598-6

M3 - Journal article

SN - 0925-1022

VL - 65

SP - 259

EP - 273

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

IS - 3

ER -

Eigenvalues and expansion of bipartite graphs

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this