# Some Results on Walk Regular and Strongly Regular Graphs

### New Zealand Journal of Mathematics

Vol. 38, (2008), Pages 161-169

M. Lepović

Department of Mathematics

Vuksanovica 32

34000, Kragujevac

Serbia (Yugoslavia)

Abstract We say that a regular graph G of order n and degree $r\ge 1$ (which is not the complete graph) is strongly regular if there exist non-negative integers τ and θ such that $|S_i\cap S_j| = \tau$ for any two adjacent vertices i and j, and $|S_i\cap S_j| = \theta$ for any two distinct non-adjacent vertices i and j, where Sk denotes the neighborhood of the vertex k. We prove that a regular G is strongly regular if and only if its vertex deleted subgraph $G_i = G\smallsetminus i$ has exactly two main eigenvalues for $i = 1, 2, \ldots, n$. In particular, we show that

$\mu_{1,2} = \frac{\tau - \theta + r \pm \sqrt{\big(\tau - \theta - r\big)^2 - 4\,\theta}}{2}\,,$

where μ1 and μ2 are the main eigenvalues of Gi. Besides, we demonstrate that if G is a conference graph then Gi is cospectral to Hi, where Hi is switching equivalent to Gi with respect to Si.

Keywords Walk regular graph, strongly regular graph, main eigenvalues, conjugate adjacency matrices

Classification (MSC2000) 05 C 50