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

Original language | English |
---|---|

Pages (from-to) | 606-614 |

Number of pages | 9 |

Journal | Linear Algebra and Its Applications |

Volume | 432 |

Issue number | 2-3 |

DOIs | |

State | Published - 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

*Linear Algebra and Its Applications*,

*432*(2-3), 606-614. https://doi.org/10.1016/j.laa.2009.09.008