EN|RU

Volume 28, No 3, 2021, P. 38-48

UDC 519.17
A. A. Makhnev and M. P. Golubyatnikov
On nonexistence of distance regular graphs with the intersection array {53, 40, 28, 16; 1, 4, 10, 28}

Abstract:
We consider $Q$-polynomial graphs of diameter 4. Apart from infinite series intersection arrays {$m(2m+1), (m-1)(2m+1), m^2, m; 1,m,m-1,m(2m+ 1)$} there are the following admissible intersection arrays of $Q$-polynomial graphs of diameter 4 with at most 4096 vertices: {5, 4, 4, 3; 1, 1, 2, 2} (odd graph on 9 vertices), {9, 8, 7, 6; 1, 2, 3, 4} (folded 9-cube), {36, 21, 10, 3; 1, 6, 15, 28} (half 9-cube), and {53, 40, 28, 16; 1, 4, 10, 28}. In the paper it is proved that a distance regular graph with an intersection array {53, 40, 28, 16; 1, 4, 10, 28} does not exist.
Bibliogr. 4.

Keywords: $Q$-polynomial graph, distance regular graph.

DOI: 10.33048/daio.2021.28.709

Aleksandr A. Makhnev 1
Mikhail P. Golubyatnikov 1

1. Krasovskii Institute of Mathematics and Mechanics,
16 Sofia Kovalevskaya Street, 620108 Yekaterinburg, Russia
e-mail: makhnev@imm.uran.ru, mike_ru1@mail.ru

Received March 31, 2021
Revised May 6, 2021
Accepted May 7, 2021

References

[1] A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs (Springer-Verlag, Heidelberg, 1989).

[2] P. Cameron, Permutation Groups (Cambridge Univ. Press, Cambridge, 1999) (London Math. Soc. Stud. Texts, Vol. 45).

[3] K. Coolsaet and A. Jurishich, Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs, J. Comb. Theory, Ser. A, 115, 1086–1095 (2008).

[4] A. L. Gavrilyuk and J. H. Koolen, A characterization of the graphs of bilinear $d \times d$-forms over $F_2$, Combinatorica 39, 289–321 (2010).

[5] A. L. Gavrilyuk and J. H. Koolen, The Terwilliger polynomial of a $Q$-polynomial distance-regular graph and its application to the pseudo-partition graphs, Linear Algebra Appl. 466, 117–140 (2015).
 © Sobolev Institute of Mathematics, 2015