M.S. Nirova. On distance-regular graphs with  $\theta_2=-1$ ... P. 215-228

Let a distance-regular graph $\Gamma$ of diameter 3 have eigenvalue $\theta_2=-1$. Then $\Delta=\bar\Gamma_3$ is a pseudo-geometric graph for $pG_{c_3}(k,b_1/c_2)$ containing $v$ Delsarte cliques $u^\bot$ of order $k+1$. In the case $a_1=0$ we have a partition of the subgraph $\Delta(u)$ by cliques $w^\bot-\{u\}$, where $w\in \Gamma(u)$. If there exists a strongly regular graph with parameters (176,49,12,14) in which neighborhoods of vertices are $7\times 7$-lattices, then there exists a distance-regular graph with intersection array $\{7,6,6;1,1,2\}$. If $\Delta$ contains an $n$-coclique $\{u,u_2,...,u_n\}$, then there are $k_3-(n-1)(a_3+1)$ vertices in $\Gamma_3(u)-\cup_{i=2}^n \Gamma(u_i)$, which yields a new upper bound for the order of a clique in $\Gamma_3$. Moreover, it is proved that distance-regular graphs with intersection arrays $\{44,35,3;1,5,42\}$ and $\{27,20,7;1,4,21\}$ do not exist.

Keywords: distance-regular graph, eigenvalue, strongly regular graph.

The paper was received by the Editorial Office on Dezember 25, 2017.

Funding Agency:

Russian Science Foundation (Grant Number 18-11-00067).

Marina Sefovna Nirova, Cand. Sci. (Phys.-Math.), Kabardino-Balkarian State University named after H.M.Berbekov, Nal’chik, 360004 Russia, e-mail: nirova_m@mail.ru.


1.   Brouwer A.E., Cohen A.M., Neumaier A. Distance-Regular Graphs. Berlin; Heidelberg; N Y: Springer-Verlag, 1989, 495 p. ISBN: 0387506195 .

2.   Makhnev A.A., Nirova M.S. Shilla distance-regular graphs with $b_2 = c_2$. Mat. Zametki, 2018, vol. 103, no. 5, pp. 730–744 (in Russian). doi: 10.4213/mzm11503 .

3.   Bang S., Koolen J. Distance-regular graphs of diameter three having eigenvalue -1. Linear Algebra Appl., 2017, vol. 531, pp. 38–53. http:10.1016/j.laa.2017.05.038 .

4.   Brouwer A.E. Polarities of G. Higman’s symmetric design and a strongly regular graph on 176 vertices // Aequationes Math. 1982. V. 25, P. 77-82.

5.   Hobart S.A., Hughes D.R. Extended partial geometries: nets and dual nets. Europ. J. Comb. 1990, vol. 11, pp. 357–372.

6.   Makhnev A.A. Partial geometries and their extensions. Russian Math. Surveys, 1999, vol.  54, no. 5, pp. 895–945.

7.   Brouwer A.E., Haemers W.H. The Gewirtz graph: an exercize in the theory of graph spectra. Europ. J. Comb. 1993, vol. 14, pp. 397–407. doi: 10.1006/eujc.1993.1044 .

8.   Behbahani M., Lam C. Strongly regular graphs with non-trivial automorphisms. Discrete Math. 2011, vol. 311, iss. 2-3 pp. 132–144. doi: 10.1016/j.disc.2010.10.005 .

9.   Cameron P. Permutation groups. Cambridge: Cambridge Univ. Press, 1999, Ser. London Math. Soc. Student Texts, vol. 45, 220 p.

10.   Gavrilyuk A.L., Makhnev A.A. On Automorphisms of a distance-regular graph with intersection array {56,45,1;1,9,56}. Dokl. Math., vol. 81, no. 3, pp. 439–442. doi: 10.1134/S1064562410030282 .

11.   Zavarnitsine A.V. Finite simple groups with narrow prime spectrum. Sibirean Electr. Math. Reports. 2009, vol. 6, pp. 1–12 (in Russian).

12.   Coolsaet K. Local structure of graph with $λ=μ=2, a_2 = 4$. Combinatorica, 1995, vol. 15, pp. 481–457.