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