|
This article is cited in 1 scientific paper (total in 1 paper)
Inverse Problems in the Class of Distance-Regular Graphs of Diameter $4$
A. A. Makhnevab, D. V. Paduchikha a N.N. Krasovskii 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 4, the graph $\Delta=\Gamma_{1,2}$ can be strongly regular. In this case, the graph $\Gamma_{3,4}$ is strongly regular and complementary to $\Delta$. Finding the intersection array of $\Gamma$ from the parameters of $\Gamma_{3,4}$ is an inverse problem. In the present paper, the inverse problem is solved in the case of an antipodal graph $\Gamma$ of diameter $4$. In this case, $r=2$ and $\Gamma_{3,4}$ is a strongly regular graph without triangles. Further, $\Gamma$ is an $AT4(p,q,r)$-graph only in the case $q=p+2$ and $r=2$. Earlier the authors proved that an $AT4(p,p+2,2)$-graph does not exist. A Krein graph is a strongly regular graph without triangles for which the equality in the Krein bound is attained (equivalently, $q^2_{22}=0$). A Krein graph $\mathrm{Kre}(r)$ with the second eigenvalue $r$ has parameters $((r^2+3r)^2,r^3+3r^2+r,0,r^2+r)$. For the graph $\mathrm{Kre}(r)$, the antineighborhood of a vertex is strongly regular with parameters $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$ and the intersection of the antineighborhoods of two adjacent vertices is strongly regularly with parameters $((r^2+2r)(r^2+2r-1),r^3+r^2-r,$ $0,r^2-r)$. Let $\Gamma$ be an antipodal graph of diameter 4, and let $\Delta=\Gamma_{3,4}$ be a strongly regular graph without triangles. In this paper it is proved that $\Delta$ cannot be a graph with parameters $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$, and if $\Delta$ is a graph with parameters $((r^2+2r)(r^2+2r-1),r^3+r^2-r,0,r^2-r)$, then $r>3$. It is proved that a distance-regular graph with intersection array $\{32,27,12(r-1)/r,1;1, 12/r,27,32\}$ exists only for $r=3$, and, for a graph with array $\{96,75,32(r-1)/r,1;1,32/r,75,96\}$, we have $r=2$.
Keywords:
distance-regular graph, antipodal graph, graph $\Gamma$ with strongly regular graph $\Gamma_{i,j}$.
Received: 14.10.2021 Revised: 19.01.2022 Accepted: 24.01.2022
Citation:
A. A. Makhnev, D. V. Paduchikh, “Inverse Problems in the Class of Distance-Regular Graphs of Diameter $4$”, Trudy Inst. Mat. i Mekh. UrO RAN, 28, no. 1, 2022, 199–208; Proc. Steklov Inst. Math. (Suppl.), 317, suppl. 1 (2022), S121–S129
Linking options:
https://www.mathnet.ru/eng/timm1891 https://www.mathnet.ru/eng/timm/v28/i1/p199
|
Statistics & downloads: |
Abstract page: | 107 | Full-text PDF : | 17 | References: | 17 | First page: | 7 |
|