Skip to main content
Article
On the Largest Eigenvalues of Bipartite Graphs Which Are Nearly Complete
Linear Algebra and its Applications (2010)
  • YI-Fan Chen, National Chiao Tung University
  • Hung-Lin Fu, National Chiao Tung University
  • In-Jae Kim, Minnesota State University, Mankato
  • Eryn M. Stehr, Georgia Southern University
  • Brendon Watts, University of Oklahoma
Abstract
For positive integers p,q,r,s and t satisfying rt⩽p and st⩽q, let G(p,q;r,s;t) be the bipartite graph with partite sets {u1,…,up} and {v1,…,vq} such that ui and vj are not adjacent if and only if there exists a positive integer k with 1⩽k⩽t such that (k-1)r+1⩽i⩽kr and (k-1)s+1⩽j⩽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⩽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.
Keywords
  • Largest,
  • Eigenvalues,
  • Bipartite graphs,
  • Nearly complete
Disciplines
Publication Date
January 15, 2010
DOI
10.1016/j.laa.2009.09.008
Citation Information
YI-Fan Chen, Hung-Lin Fu, In-Jae Kim, Eryn M. Stehr, et al.. "On the Largest Eigenvalues of Bipartite Graphs Which Are Nearly Complete" Linear Algebra and its Applications Vol. 432 Iss. 2-3 (2010) p. 606 - 614 ISSN: 0024-3795
Available at: http://works.bepress.com/eryn-stehr/2/