On the largest eigenvalues of bipartite graphs which are nearly complete

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 {u(1), ..., u(p)} and {v(1), ..., v(q)} such that u(i) and v(j) 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 vertical bar U vertical bar = p and vertical bar V vertical bar = 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. (C) 2009 Elsevier Inc. All rights reserved.