On the largest eigenvalues of bipartite graphs which are nearly complete

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

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Scopus citations

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

Original languageEnglish
Pages (from-to)606-614
Number of pages9
JournalLinear Algebra and Its Applications
Volume432
Issue number2-3
DOIs
StatePublished - 15 Jan 2010

Keywords

  • Bipartite graph
  • Eigenvector
  • Largest eigenvalue

Fingerprint Dive into the research topics of 'On the largest eigenvalues of bipartite graphs which are nearly complete'. Together they form a unique fingerprint.

  • Cite this