УДК 519.17
MSC: 05C25
DOI: 10.21538/0134-4889-2018-24-2-215-228
Полный текст статьи
Работа выполнена при поддержке гранта РНФ, проект 18-11-00067.
Пусть дистанционно регулярный граф $\Gamma$ диаметра 3 имеет собственное значение $\theta_2=-1$. Тогда $\Delta=\bar \Gamma_3$ является псевдогеометрическим графом для $pG_{c_3}(k,b_1/c_2)$, содержащим $v$ клик Дельсарта вида $u^\bot$ порядка $k+1$. В случае $a_1=0$ имеем разбиение подграфа $\Delta(u)$ кликами $w^\bot-\{u\}$, $w\in \Gamma(u)$. Если существует сильно регулярный граф с параметрами (176,49,12,14), в котором окрестности вершин являются $7\times 7$-решетками, то существует и дистанционно регулярный граф с массивом пересечений $\{7,6,6;1,1,2\}$. Если $\Delta$ содержит $n$-коклику $\{u,u_2,...,u_n\}$, то $\Gamma_3(u)-\cup_{i=2}^n \Gamma(u_i)$ содержит $k_3-(n-1)(a_3+1)$ вершин. Отсюда получается новая верхняя граница для порядка клики в $\Gamma_3$. Более того, доказано, что дистанционно регулярные графы с массивами пересечений $\{44,35,3;1,5,42\}$ и $\{27,20,7;1,4,21\}$ не существуют.
Ключевые слова: дистанционно регулярный граф, собственное значение, сильно регулярный граф.
СПИСОК ЛИТЕРАТУРЫ
1. Brouwer A. E., Cohen A. M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; N Y: Springer-Verlag, 1989. 495 p. ISBN: 0387506195 .
2. Махнев А. А., Нирова М. С. Дистанционно регулярные графы Шилла с $b_2 = c_2$ // Мат. заметки. 2018. Т. 103, № 5. C. 730–744. doi: 10.4213/mzm11503 .
3. Bang S., Koolen J. Distance-regular graphs of diameter three having eigenvalue -1 // Linear Algebra Appl. 2017. Vol. 531. P. 38–53. http:10.1016/j.laa.2017.05.038 .
4. Brouwer A. E. Polarities of G. Higman’s symmetric design and a strongly regular graph on 176 vertices // Aequationes Math. 1982. Vol. 25. P. 77-82.
5. Hobart S. A., Hughes D. R. Extended partial geometries: nets and dual nets // Europ. J. Comb. 1990. Vol. 11. P. 357–372.
6. Махнев А. А. Частичные геометрии и их расширения // Успехи матем. наук 1999. Т. 54, № 5. С. 21–72.
7. Brouwer A.E., Haemers W.H. The Gewirtz graph: an exercize in the theory of graph spectra // Europ. J. Comb. 1993. Vol. 14. P. 397–407. doi: 10.1006/eujc.1993.1044 .
8. Behbahani M., Lam C. Strongly regular graphs with non-trivial automorphisms // Discrete Math. 2011. Vol. 311, iss. 2-3. P. 132–144. doi: 10.1016/j.disc.2010.10.005 .
9. Cameron P. Permutation groups. Cambridge: Cambridge Univ. Press, 1999. 220 p. (London Math. Soc. Student Texts; vol. 45.)
10. Гаврилюк А.Л., Махнев А.А. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {56,45,1;1,9,56} // Докл. РАН 2010. Т. 432, № 5. С. 583–587.
11. Zavarnitsine A.V. Finite simple groups with narrow prime spectrum // Sibirean Electr. Math. Reports. 2009. Vol. 6. P. 1–12.
12. Coolsaet K. Local structure of graph with $λ=μ=2, a_2 = 4$ // Combinatorica. 1995. Vol. 15. P. 481–457.
Поступила 25.12.2017
Нирова Марина Сефовна
канд. физ.-мат. наук, доцент
Кабардино-балкарский государственный университет имени Х.М. Бербекова,
г. Нальчик
e-mail: nirova_m@mail.ru
English
M. S. Nirova. On distance-regular graphs with $\theta_2=-1$
Let a distance-regular graph $\Gamma$ of diameter 3 have eigenvalue $\theta_2=-1$. Then $\Delta=\bar\Gamma_3$ is a pseudo-geometric graph for $pG_{c_3}(k,b_1/c_2)$ containing $v$ Delsarte cliques $u^\bot$ of order $k+1$. In the case $a_1=0$ we have a partition of the subgraph $\Delta(u)$ by cliques $w^\bot-\{u\}$, where $w\in \Gamma(u)$. If there exists a strongly regular graph with parameters (176,49,12,14) in which neighborhoods of vertices are $7\times 7$-lattices, then there exists a distance-regular graph with intersection array $\{7,6,6;1,1,2\}$. If $\Delta$ contains an $n$-coclique $\{u,u_2,...,u_n\}$, then there are $k_3-(n-1)(a_3+1)$ vertices in $\Gamma_3(u)-\cup_{i=2}^n \Gamma(u_i)$, which yields a new upper bound for the order of a clique in $\Gamma_3$. Moreover, it is proved that distance-regular graphs with intersection arrays $\{44,35,3;1,5,42\}$ and $\{27,20,7;1,4,21\}$ do not exist.
Keywords: distance-regular graph, eigenvalue, strongly regular graph.
The paper was received by the Editorial Office on Dezember 25, 2017.
Funding Agency:
Russian Science Foundation (Grant Number 18-11-00067).
Marina Sefovna Nirova, Cand. Sci. (Phys.-Math.), Kabardino-Balkarian State University named after H.M.Berbekov, Nal’chik, 360004 Russia, e-mail: nirova_m@mail.ru.
[References on the English button bottom right]
