Some Results on Walk Regular and Strongly Regular Graphs


Jump to: navigation, search

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

Full text

Full paper

Personal tools