Дистанционно регулярные графы с массивами пересечений {7,6,6;1,1,2} и {42,30,2;1,10,36} не существуют

Автор: Махнев Александр Алексеевич, Биткина Виктория Васильевна, Гутнова Алина Казбековна

Журнал: Владикавказский математический журнал @vmj-ru

Статья в выпуске: 4 т.23, 2021 года.

Бесплатный доступ

Пусть Γ - дистанционно регулярный граф диаметра 3 без треугольников, u - вершина графа Γ, Δi=Γi(u) и Σi=Δi2,3. Тогда Σi - регулярный граф без 3-коклик степени k′=ki-ai-1 на v′=ki вершинах. Заметим, что для несмежных вершин y,z∈Σi имеем Σi={y,z}∪Σi(y)∪Σi(z). Поэтому для μ′=|Σi(y)∩Σi(z)| имеем равенство v′=2k′+2-μ′. Отсюда граф Σ является кореберно регулярным с параметрами (v′,k′,μ′). В работе доказано, что дистанционно регулярный граф с массивом пересечений {7,6,6;1,1,2} не существует. В статье М. С. Нировой "On distance-regular graphs with θ2=-1" показано, что если существует сильно регулярный граф с параметрами (176,49,12,14), в котором окрестности вершин являются 7×7-решетками, то существует и дистанционно регулярный граф с массивом пересечений {7,6,6;1,1,2}. М.~П. Голубятников заметил, что для дистанционно регулярного графа Γ с массивом пересечений {7,6,6;1,1,2} граф Γ2 является дистанционно регулярным с массивом пересечений {42,30,2;1,10,36}. С помощью этого результата и вычисления тройных чисел пересечений доказано, что дистанционно регулярные графы с массивами пересечений {7,6,6;1,1,2} и {42,30,2;1,10,36} не существуют.

Еще

Дистанционно регулярный граф, граф без треугольников, тройные числа пересечений

Короткий адрес: https://sciup.org/143177822

IDR: 143177822   |   DOI: 10.46698/y2738-1800-0363-i

Список литературы Дистанционно регулярные графы с массивами пересечений {7,6,6;1,1,2} и {42,30,2;1,10,36} не существуют

  • Brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs. Berlin, Heidelberg, New York: Springer-Verlag, 1989.
  • Fon Der Flaas D. There exists no distance-regular graph with intersection array \\(\\{5,4,3;1,1,2//) // Europ. J. Comb. 1993. Vol. 14, № 5. P. 409-412. DOI: 10.1006/eujc.1993.1045
  • Нирова М. С. О дистанционно регулярных графах с θ2=-1 // Тр. Ин-та мат. и мех. УрО РАН. 2018. Т. 24, № 2. С. 215-228. DOI: 10.21538/0134-4889-2018-24-2-215-228
  • Coolsaet K., Jurishich A. Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs // J. Comb. Theory. Ser. A. 2008. Vol. 115, № 6. P. 1086-1095. DOI: 10.1016/j.jcta.2007.12.001
  • Махнев А. А., Нирова М. С. Дистанционно регулярные графы Шилла с b2=c2 // Мат. заметки. 2018. Т. 103, № 5. С. 730-744. DOI: 10.4213/mzm11503
Статья научная