Регистрация / Вход
Прислать материал

О вершинной связности графов Деза, имеющих параметры графов, дополнительных к зейделевым

Сведения об участнике
ФИО
Панасенко Дмитрий Игоревич
Вуз
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Челябинский государственный университет"
Тезисы (информация о проекте)
Область наук
Математика. Механика
Раздел области наук
Математика
Тема
О вершинной связности графов Деза, имеющих параметры графов, дополнительных к зейделевым
Резюме
В данной работе рассматривается вершинная связность графов Деза, полученные из сильно регулярных графов с собственным значением 𝑟 = 1 (т.е. из дополнительных к зейделевым). Результат исследования: у графов, полученных из дополнений к 𝑛 × 𝑛-решетке вершинная связность на 1 меньше валентности, у остальных графов равна валентности.
Ключевые слова
графы, сильно регулярные графы, графы Деза, вершинная связность,
Цели и задачи
Исследовать вершинную связность графов Деза, полученных из дополнений к графам из теоремы 3 с помощью автоморфизма порядка 2, переставляющего только несмежные вершины.
Введение

Вершинная связность графа является одной из его характеристик, интересных и с практической, и с теоретической точек зрения. Для отдельных классов графов известны оценки и точные результаты: например, вершинная связность k-регулярного графа
Кэли не меньше 2/3 (�� + 1), а вершинная связность дистанционно регулярного графа равна его валентности. 

Графы Деза принято рассматривать как обобщение сильно регулярных графов.

В работе А. Л. Гаврилюка, С. В. Горяинова, В. В. Кабанова была исследована вершинная связность графов Деза, полученных из
сильно регулярных графов с помощью особой конструкции, при
этом случай собственного значения �� ≤ 2 остался нерассмотренным.

Мы исследовали графы Деза, полученные из сильно регулярных графов с параметром �� = 1.

Методы и материалы

Вершинная связность исслеовалась с помощью компьютерного перебора и Теоремы Менгера. 

Описание и обсуждение результатов

Теорема 5. Пусть Δ – граф Деза, полученный из сильно регулярного графа с
собственным значением �� = 1. Тогда имеет место один из следующих случаев:
1. Δ получен из дополнения к одному из спорадических графов (4)-(8), его вершин-
ная связность равна валентности;
2. Δ получен из дополнения к полному многодольному графу с долями порядка 2,
которое является несвязным (объединение изолированных ребер), вопрос вершинной
связности тривиален;
3. Δ получен из дополнения к треугольному графу ��(��), �� ≥ 4, его вершинная
связность равна валентности;
4. Δ получен из дополнения к �� × ��-решетке, �� ≥ 3, его вершинная связность
равна �� − 1, где �� – валентность.
В дальнейшем можно продолжить исследование вершинной связности графов
Деза, полученных из сильно регулярных с собственным значением �� = 2. Такие графы
классифицированы, среди них существуют три гипотетически бесконечные
серии параметров графов, но для многих явно указанных параметров открыт вопрос
существования соответствующих графов. Поэтому к данному вопросу нужно искать
подход, отличный от использованного в работе.

Используемые источники
[1] Brouwer A.E., Mesner D.M. The connectivity of strongly regular graphs // Europ. J.
Combin – 1985 – Vol. 6 – P. 215–216.
[2] Brouwer A.E., Koolen J.H. The vertex-connectivity of a distance-regular graph //
Europ. J. Combin – 2009 – Vol. 30, no. 3 – P. 668–673.
[3] M. Erickson, S. Fernando, W.H. Haemers, D. Hardy, J. Hemmeter. Deza graphs: A
generalization of strongly regular graphs // J. Comb. Des – 1999 – Vol. 7, no. 6 – P.
359–405.
[4] А. Л. Гаврилюк, С. В. Горяинов, В. В. Кабанов. О вершинной связности графов
Деза // Тр. Ин-та математики и механики УрО РАН – 2013 – Т. 19, № 3 – С. 94–103
[5] С. В. Горяинов, Л. В. Шалагинов. О графах Деза с параметрами графов, дополни-
тельных к треугольным и решeтчатым // Дискретн. анализ и исслед. опер. – 2013
– Т. 20, № 2 – С. 3–14
Information about the project
Surname Name
Panasenko Dmitry
Project title
On the vertex connectivity of Deza graphs, with the parameters that are additional to Seidel пкфзры
Summary of the project
In this paper we consider the vertex connectivity of Deza graphs derived from strongly regular graphs with eigenvalue 𝑟 = 1 (ie from additional to Seidel). The result of the study: in the graphs obtained from additions to 𝑛 × 𝑛-lattice vertex connectivity to 1 less than the valence, the remaining Counts equal valence.
Keywords
graphs, strongly regular graphs, Deza graphs, vertex connectivity