標題: On the largest eigenvalues of bipartite graphs which are nearly complete
作者: Chen, Yi-Fan
Fu, Hung-Lin
Kim, In-Jae
Stehr, Eryn
Watts, Brendon
應用數學系
Department of Applied Mathematics
關鍵字: Bipartite graph;Eigenvector;Largest eigenvalue
公開日期: 15-Jan-2010
摘要: 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.
URI: http://dx.doi.org/10.1016/j.laa.2009.09.008
http://hdl.handle.net/11536/5963
ISSN: 0024-3795
DOI: 10.1016/j.laa.2009.09.008
期刊: LINEAR ALGEBRA AND ITS APPLICATIONS
Volume: 432
Issue: 2-3
起始頁: 606
結束頁: 614
Appears in Collections:Articles


Files in This Item:

  1. 000272929800014.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.