×

zbMATH — the first resource for mathematics

The second largest eigenvalues of regular bipartite graphs. (English) Zbl 0990.05095
Introduction: Let \(\Gamma\) be a bipartite graph with parts \(V_1\) and \(V_2\). We order the vertices of \(\Gamma\) so that those in \(V_1\) come first. Then the adjacency matrix of \(\Gamma\) is of the form \[ A= \begin{pmatrix} 0 & B\\ {^tB} & 0\end{pmatrix}. \] A bipartite graph is called semiregular of degree \((r,s)\) if each vertex in \(V_1\) has degree \(r\) and each vertex in \(V_2\) has degree \(s\).
In this paper we study spectra of regular (or semiregular) bipartite graphs. Connected regular bipartite graphs with exactly four distinct eigenvalues are the incidence graphs of symmetric designs. In Section 2 we study regular bipartite graphs with exactly five distinct eigenvalues. The notion of generalized symmetric design graphs is introduced in Section 4 and we prove that such graphs are Ramanujan graphs. The incidence graphs of symmetric designs, the incidence graphs of the partial geometry \(\text{pg}(K,K,T)\) and regular generalized polygons are generalized symmetric design graphs. In the final section we study the second largest eigenvalues of regular bipartite graphs. We shall prove that for a given positive number \(\lambda_2\) there are only finitely many bipartite distance-regular graphs (DRGs) of diameter \(\geq 5\) with the second largest eigenvalue \(\lambda_2\). In Theorem 7.5 we shall prove that if \(\Gamma\) is a bipartite DRG with diameter 4 and its second largest eigenvalues is \(\sqrt p\) for some prime number \(p\), then it is the incidence graph of the affine plane \(\text{AG}(2,p)\) minus a parallel class. As final result, all connected regular bipartite graphs with the second largest eigenvalue \(\lambda_2\leq \sqrt 2\) and all bipartite DRGs with the second largest eigenvalue \(\lambda_2\leq\sqrt 3\) are determined.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05E30 Association schemes, strongly regular graphs
PDF BibTeX XML Cite
Full Text: DOI