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 | 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 .