RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2018 Volume 24, Number 3, Pages 133–144 (Mi timm1557)

This article is cited in 2 papers

Inverse problems in distance-regular graphs theory

A. A. Makhnevab, D. V. Paduchikha

a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg

Abstract: For a distance-regular graph $\Gamma$ of diameter 3, the graph $\Gamma_i$ can be strongly regular for $i=2$ or $3$. Finding the parameters of $\Gamma_i$ given the intersection array of $\Gamma$ is a direct problem, and finding the intersection array of $\Gamma$ given the parameters of $\Gamma_i$ is the inverse problem. The direct and inverse problems were solved earlier by A.A. Makhnev and M.S. Nirova for $i=3$. In the present paper, we solve the inverse problem for $i=2$: given the parameters of a strongly regular graph $\Gamma_2$, we find the intersection array of a distance-regular graph $\Gamma$ of diameter 3. It is proved that $\Gamma_2$ is not a graph in the half case. We also refine Nirova's results on distance-regular graphs $\Gamma$ of diameter 3 for which $\Gamma_2$ and $\Gamma_3$ are strongly regular. New infinite series of admissible intersection arrays are found: $\{r^2+3r+1,r(r+1),r+2;1,r+1,r(r+2)\}$ for odd $r$ divisible by 3 and $\{2r^2+5r+2,r(2r+2),2r+3;1,2r+2,r(2r+3)\}$ for $r$ indivisible by $3$ and not congruent to $\pm 1$ modulo $5$.

Keywords: strongly regular graph, distance-regular graph, intersection array.

UDC: 519.17

MSC: 05C25

Received: 11.05.2018

DOI: 10.21538/0134-4889-2018-24-3-133-144


 English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2019, 307, suppl. 1, S88–S98

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025