TY - JOUR

T1 - On the largest eigenvalues of bipartite graphs which are nearly complete

AU - Chen, Yi Fan

AU - Fu, Hung-Lin

AU - Kim, In Jae

AU - Stehr, Eryn

AU - Watts, Brendon

PY - 2010/1/15

Y1 - 2010/1/15

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

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

KW - Bipartite graph

KW - Eigenvector

KW - Largest eigenvalue

UR - http://www.scopus.com/inward/record.url?scp=70449685733&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2009.09.008

DO - 10.1016/j.laa.2009.09.008

M3 - Article

AN - SCOPUS:70449685733

VL - 432

SP - 606

EP - 614

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 2-3

ER -