Abstract
<div class="line" id="line-5"> 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.</div>
Original language | American English |
---|---|
Journal | Linear Algebra and Its Applications |
Volume | 432 |
DOIs | |
State | Published - Jan 15 2010 |
Disciplines
- Mathematics
Keywords
- Bipartite graphs
- Eigenvalues
- Largest
- Nearly complete