# 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
Full Text: