Inverse Problems in the Class of Distance-Regular Graphs of Diameter $4$

A. A. Makhnev   ; D. V. Paduchikh

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 1, pp. 199-208

Résumé

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$.

Détail

Keywords: distance-regular graph, graph $\Gamma$ with strongly regular graph $\Gamma_{i,j}$.
Mots-clés : antipodal graph

Bibliographie

[1] Brouwer A. E., Cohen A. M., Neumaier A., Distance-regular graphs, Springer-Verlag, Berlin; Heidelberg; NY, 1989, 495 pp. | MR | Zbl

[2] Jurisic A., Koolen J., Terwilliger P., “Tight distance-regular graphs”, J. Algebr. Comb., 12 (2000), 163–197 | DOI | MR | Zbl

[3] Makhnev A. A., Nirova M. S., “Distantsionno regulyarnye grafy Shilla s $b_2=c_2$”, Mat. zametki, 103:4 (2018), 730–744 | DOI | Zbl

[4] Soicher L., “The uniqueness of a distance-regular graph with intersection array $\{32,27,8,1;1,4,27,32\}$ and related results”, Des. Codes Cryptogr., 84 (2017), 101–108 | DOI | MR | Zbl

[5] Gavrilyuk A. L., Makhnev A. A., “O grafakh Kreina bez treugolnikov”, Dokl. RAN, 403:6 (2005), 727–730 | MR | Zbl

[6] Makhnev A. A., “Graf Kreina $Kre(4)$ ne suschestvuet”, Dokl. RAN, 475:3 (2017), 251–253 | DOI | Zbl

[7] Makhnev A. A., Paduchikh D. V., “O silno regulyarnykh grafakh s sobstvennym znacheniem $\mu$ i ikh avtomorfizmakh”, Tr. In-ta matematiki i mekhaniki UrO RAN, 19:3 (2013), 207–214 | MR

[8] Vidali J., “Using symbolic computation to prove nonexistence of distance-regular graphs”, Electronic J. Sombinatorics, 25:4 (2018), 4.21 | DOI | MR | Zbl

[9] Gavrilyuk A. L., Makhnev A. A., Paduchikh D. V., “Distantsionno regulyarnye grafy, v kotorykh okrestnosti vershin izomorfny grafu Gevirttsa”, Tr. In-ta matematiki i mekhaniki UrO RAN, 16:2 (2010), 35–47

[10] Jurishich A., Koolen J., “Classification of the $AT4(qs,q,q)$ family of distance-regular graphs”, J. Comb. Theory, 118:3 (2011), 842–852 | DOI | MR

[11] Bamberg J., etc., GAP 4, Package FinInG, 2018, 314 pp. URL: https://www.gap-system.org/Manuals/pkg/fining/doc/manual.pdf

[12] Efimov K. S., “Avtomorfizmy $AT4(4,4,2)$-grafa i otvechayuschikh emu silno regulyarnykh grafov”, Tr. In-ta matematiki i mekhaniki UrO RAN, 23:4 (2017), 119–127