On the largest eigenvalues of bipartite graphs which are nearly complete

Yi Fan Chen, Hung-Lin Fu, In Jae Kim*, Eryn Stehr, Brendon Watts

*此作品的通信作者

研究成果: Article同行評審

7 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)606-614
頁數9
期刊Linear Algebra and Its Applications
432
發行號2-3
DOIs
出版狀態Published - 15 一月 2010

指紋

深入研究「On the largest eigenvalues of bipartite graphs which are nearly complete」主題。共同形成了獨特的指紋。

引用此