Eigenvalues and expansion of bipartite graphs

Tom Høholdt, Heeralal Janwa

    Research output: Contribution to journalJournal articleResearchpeer-review

    1662 Downloads (Pure)

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

    Keywords

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

    Fingerprint Dive into the research topics of 'Eigenvalues and expansion of bipartite graphs'. Together they form a unique fingerprint.

    Cite this