Eigenvalues and expansion of bipartite graphs

Publication: Research - peer-reviewJournal article – Annual report year: 2010

Documents

View graph of relations

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 languageEnglish
JournalDesigns, Codes and Cryptography
Volume65
Issue number3
Pages (from-to)259-273
ISSN0925-1022
StatePublished - 2012
Peer-reviewedYes

Keywords

  • Bipartite graphs, Expander graphs, Isoperimetric constant, Eigenvalues of graphs, Bipartite Ramanujan graphs, BIBD’s, Generalized N-gons, LDPC codes
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 5477845