A.A. Makhnev, D. V. Paduchikh. Inverse problems in the class of distance-regular graphs of diameter 4 ... P. 199-208

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 November 14, 2021

Revised January 19, 2022

Accepted January 24, 2022

Funding Agency: This work was supported by the Russian Foundation for Basic Research — the National Natural Science Foundation of China (project no. 20-51-53013).

Aleksandr Alekseevich Makhnev, Dr. Phys.-Math. Sci., Corresponding member of RAS, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal Univercity, Yekaterinburg, 620002 Russia, e-mail: makhnev@imm.uran.ru

Dmitrii Viktorovich Paduchikh, Dr. Phys.-Math. Sci., Prof. of RAS, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: dpaduchikh@gmail.com

REFERENCES

1.   Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; New York: Springer-Verlag, 1989, 495 p. ISBN: 0387506195 .

2.   Jurisic A., Koolen J., Terwilliger P. Tight distance-regular graphs. J. Algebr. Comb., 2000, vol. 12, no. 2, pp. 163–197. doi: 10.1023/A:1026544111089 

3.   Makhnev A.A., Nirova M.S. Distance-regular Shilla graphs with $b_2=c_2$. Math. Notes, 2018, vol. 103, no. 5, pp. 780–792. doi: 10.1134/S0001434618050103 

4.   Soicher L.H. The uniqueness of a distance-regular graph with intersection array {32,27,8,1;1,4,27,32} and related results. Des. Codes Cryptogr., 2017, vol. 84, no. 1, pp. 101–108. doi: 10.1007/s10623-016-0223-6 

5.   Gavrilyuk A.L., Makhnev A.A. On Krein graphs without triangles. Dokl. Math., 2005, vol. 72, no. 1, pp. 591–594.

6.   Makhnev A.A. The graph Kre(4) does not exist. Dokl. Math., 2017, vol. 96, no. 1, pp. 348–350. doi: 10.1134/S1064562417040123 

7.   Makhnev A.A., Paduchikh D.V. On strongly regular graphs with eigenvalue μ and their extensions. Proc. Steklov Inst. Math. (Suppl.), 2014, vol. 285, suppl. 1, pp. S128–S135. doi: 10.1134/S0081543814050137 

8.   Vidali J. Using symbolic computation to prove nonexistence of distance-regular graphs. Electronic J. Сombinatorics, 2018, vol. 25, no. 4, art. no. 4.21. doi: 10.37236/7763 

9.   Gavrilyuk A.L., Makhnev A.A., Paduchikh D.V. Distance-regular graphs in which neighborhoods of vertices are isomorphic to the Gewirtz graph. Trudy Inst. Mat. i Mekh. UrO RAN, 2010, vol. 16, no. 2, pp. 35–47 (in Russian).

10.   Jurishich A., Koolen J. Classification of the AT4(qs,q,q) family of distance-regular graphs. J. Combinatorial Theory, Series A, 2011, vol. 118, no. 3, pp. 842–852. doi: 10.1016/j.jcta.2010.10.001 

11.   Bamberg J., etc. GAP 4, Package FinInG. Available on: https://www.gap-system.org/Manuals/pkg/fining/doc/manual.pdf 

12.   Efimov K.S. Automorphisms of an AT4(4,4,2)-graph and of the corresponding strongly regular graphs. Proc. Steklov Inst. Math. (Suppl.), 2019, vol. 304, suppl. 1, pp. S59–S67. doi: 10.1134/S008154381902007X 

Cite this article as: A.A. Makhnev, D.V. Paduchikh. Inverse problems in the class of distance-regular graphs of diameter 4, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 1, pp. 199–208; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2022, Vol. 317, Suppl. 1, pp. S121–S129.