Median eigenvalues of bipartite graphs

2013/12/09 by Mohar, Bojan, Tayfeh-Rezaie, Behruz · 1 citation
#05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1312.2613

Abstract

For a graph G of order n and with eigenvalues λ₁\geqslant⋯\geqslantλ_n, the HL-index R(G) is defined as R(G) =max\|λ_{\lfloor(n+1)/2\rfloor}|, |λ_{\lceil(n+1)/2\rceil}|\. We show that for every connected bipartite graph G with maximum degree Δ\geqslant3, R(G)\leqslant√(Δ-2) unless G is the the incidence graph of a projective plane of order Δ-1. We also present an approach through graph covering to construct infinite families of bipartite graphs with large HL-index.

Cited by

• Finite projective planes meet spectral gaps

Related

• Median eigenvalues and the HOMO-LUMO index of graphs
• Maxima of the Q-index: graphs with no K_s,t
• Some New Lower Bounds for the Estrada Index
• The Largest Eigenvalue and Bi-Average Degree of a Graph
• On maximum Estrada indices of bipartite graphs with some given parameters