УДК 512.542+519.177
MSC: 05C25, 20D06
DOI: 10.21538/0134-4889-2022-28-2-258-268
Полный текст статьи (Full text)
The work is supported by the Russian Science Foundation (project no. 19-71-10067).
This paper is based on the results of the 2021 Conference of International Mathematical Centers “Groups and Graphs, Semigroups and Synchronization".
A simple $k$-regular graph with $v$ vertices is an amply regular graph with parameters $(v, k, \lambda, \mu)$ if any two adjacent vertices have exactly $\lambda$ common neighbors and any two vertices which are at distance $2$ in this graph have exactly $\mu$ common neighbors. Let $G$ be a finite group, $H \le G$, ${\mathfrak{H}} = \{H^g \,|\, g \in G \}$ be the corresponding conjugacy class of subgroups of $G$, and $1 \le d $ be an integer. We construct a simple graph $\Gamma(G, H, d)$ as follows. The vertices of $\Gamma(G, H, d)$ are the elements of ${\mathfrak{H}}$, and two vertices $H_1$ and $H_2$ from ${\mathfrak{H}}$ are adjacent in $\Gamma(G, H, d)$ if and only if $|H_1 \cap H_2| = d$. In this paper we prove that if $q$ is a prime power with $13 \le q \equiv 1 \pmod{4}$, $G=SL_2(q)$, and $H$ is a dihedral maximal subgroup of $G$ of order $2(q-1)$, then the graph $\Gamma(G, H, 8)$ is a vertex-primitive arc-transitive amply regular graph with parameters $\left(\dfrac{q(q+1)}{2}, \dfrac{q-1}{2}, 1, 1\right)$ and with ${\rm Aut}(PSL_2(q))\le {\rm Aut}(\Gamma)$. Moreover, we prove that $\Gamma(G, H, 8)$ has a perfect $1$-code, in particular, its diameter is more than $2$.
Keywords: finite simple group, arc-transitive graph, amply regular graph, edge-regular graph, graph of girth 3, Deza graph, perfect 1-code
REFERENCES
1. Akers S.B., Harel D., and Krishnamurthy B. The star graph: an attractive alternative to the n-cube. Proc. Int. Conf. Parallel Processing, 1987, pp. 393–400.
2. Bray J.N., Holt D.F., Roney-Dougal C.M. The maximal subgroups of the low-dimensional finite classical groups. Cambridge: Cambridge Univ. Press, 2013, 438 p. doi: 10.1017/CBO9781139192576
3. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin etc: Springer-Verlag, 1989, 495 p. ISBN: 3-540-50619-5 .
4. GAP — Groups, Algorithms, Programming – a system for computational discrete algebra, Version 4.10.1, 2019. Available on: https://www.gap-system.org
5. Godsil C., Royle G. Algebraic graph theory. NY: Springer, 2001, 443 p. doi: 10.1007/978-1-4613-0163-9
6. Koblitz N. Finite fields and quadratic residues. In: A course in number theory and cryptography. Ser. Graduate Texts in Mathematics, vol. 114. NY: Springer, 1994, pp. 31–53. doi: 10.1007/978-1-4419-8592-7_2
7. Lakshmivarahan S., Jwo J.-S., Dhall S.K. Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey. Parallel Comput., 1993, vol. 19, pp. 361–407. doi: 10.1016/0167-8191(93)90054-O
8. Lovasz L. Combinatorial structures and their applications. In: Proc. Calgary Internat. Conf. Calgary, Alberta, 1969. NY: Gordon and Breach, 1970, pp. 243–246.
9. Marusic D. and Scapellato R. A class of non-Cayley vertex-transitive graphs associated with $PSL(2,p)$. Discrete Math., 1992, vol. 109, no. 1-3, pp. 161–170. doi: 10.1016/0012-365X(92)90287-P
10. Maslova N.V. Classification of maximal subgroups of odd index in finite simple classical groups: Addendum. Siberian Electron. Math. Reports, 2018, vol. 15, pp. 707–718. doi: 10.17377/semi.2018.15.056
11. Mulder M. (0,λ)-graphs and n-cubes. Discrete Math., 1979, vol. 28, no. 2, pp. 179–188.
12. Ray B.N.B. Parallel algorithm for Hermite interpolation on the star graph. International J. Advanced Research in Comp. Sci. and Soft. Engineering, 2015, vol. 5, no. 5, pp. 1019–1026.
Received March 11, 2022
Revised May 6, 2022
Accepted May 11, 2022
Funding Agency: This work was supported by the Russian Science Foundation (project no. 19-71-10067).
Mikhail Petrovich Golubyatnikov, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: mike_ru1@mail.ru
Natalia Vladimirovna Maslova, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Prof., Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: butterson@mail.ru
Cite this article as: M.P. Golubyatnikov, N.V. Maslova. On a class of vertex-primitive arc-transitive amply regular graphs, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 2, pp. 258–268.
Русский
М.П. Голубятников, Н.В. Маслова. О классе вершинно-примитивных транзитивных на дугах вполне регулярных графов
Обыкновенный $k$-регулярный граф с $v$ вершинами называется вполне регулярным с параметрами $(v, k, \lambda, \mu)$, если любые две смежные вершины имеют точно $\lambda$ общих соседей, а любые вершины, находящиеся на расстоянии $2$ в этом графе, имеют точно $\mu$ общих соседей. Пусть $G$ — конечная группа, $H \le G$, ${\mathfrak{H}} = \{H^g \,|\, g \in G \}$ — соответствующий класс сопряженности подгрупп группы $G$ и $1\le d $ — целое число. Построим обыкновенный граф $\Gamma(G, H, d)$ следующим образом{\rm:} вершинами графа $\Gamma(G, H, d)$ являются элементы класса ${\mathfrak{H}}$, и две различные вершины $H_1$ и $H_2$ из ${\mathfrak{H}}$ смежны в $\Gamma(G, H, d)$ тогда и только тогда, когда $|H_1 \cap H_2| = d$. В данной работе мы доказываем, если $q$ — степень простого числа такая, что $13 \le q \equiv 1 \pmod{4}$, $G=SL_2(q)$ и $H$ — диэдральная максимальная подгруппа группы $G$ порядка $2(q-1)$, то граф $\Gamma=\Gamma(G, H, 8)$ является вершинно примитивным транзитивным на дугах вполне регулярным графом с параметрами $\left(\dfrac{q(q+1)}{2}, \dfrac{q-1}{2}, 1, 1\right)$, при этом ${\rm Aut}(PSL_2(q)) \le {\rm Aut}(\Gamma)$. Более того, мы показываем, что $\Gamma=\Gamma(G, H, 8)$ содержит совершенный $1$-код, в частности, диаметр этого графа больше $2$.
Ключевые слова: конечная простая группа, транзитивный на дугах граф, вполне регулярный граф, реберно регулярный граф, граф обхвата 3, граф Деза, совершенный 1-код
