On the Largest Eigenvalues of Bipartite Graphs Which Are Nearly Complete

YI-Fan Chen, Hung-Lin Fu, In-Jae Kim, Eryn M. Stehr, Brendon Watts

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

<div class="line" id="line-5"> For positive integers p,q,r,s and t satisfying rt&les;p and st&les;q, let G(p,q;r,s;t) be the bipartite graph with partite sets {u1,&hellip;,up} and {v1,&hellip;,vq} such that ui and vj are not adjacent if and only if there exists a positive integer k with 1&les;k&les;t such that (k-1)r+1&les;i&les;kr and (k-1)s+1&les;j&les;ks. In this paper we study the largest eigenvalues of bipartite graphs which are nearly complete. We first compute the largest eigenvalue (and all other eigenvalues) of G(p,q;r,s;t), and then list nearly complete bipartite graphs according to the magnitudes of their largest eigenvalues. These results give an affirmative answer to [1, Conjecture 1.2] when the number of edges of a bipartite graph with partite sets U and V, having |U|=p and |V|=q for p&les;q, is pq-2. Furthermore, we refine [1, Conjecture 1.2] for the case when the number of edges is at least pq-p+1.</div>
Original languageAmerican English
JournalLinear Algebra and Its Applications
Volume432
DOIs
StatePublished - Jan 15 2010

Disciplines

  • Mathematics

Keywords

  • Bipartite graphs
  • Eigenvalues
  • Largest
  • Nearly complete

Fingerprint

Dive into the research topics of 'On the Largest Eigenvalues of Bipartite Graphs Which Are Nearly Complete'. Together they form a unique fingerprint.

Cite this