СВЯЗНОСТЬ ВТОРОЙ ОКРЕСТНОСТИ В КОРЕБЕРНО-РЕГУЛЯРНЫХ ГРАФАХ ДЕЗА

Горяинов Сергей Викторович, преподаватель ИММ УрО РАН, г. Екатеринбург. E-mail: 44g@mail.ru

Исакова Галина Сергеевна, студент ФГБОУ ВПО «ЧелГУ», г. Челябинск. E-mail: carleink@gmail.com

В работе классифицированы кореберно-регулярные графы Деза с несвязной второй окрестностью. В целом решена классическая задача комбинаторики и теории графов, в частности, перечисление комбинаторных объектов с заданными свойствами. Изучение графов Деза представляет интерес в связи с тем, что графы Деза имеют диаметр 2 и являются естественным обобщением сильно регулярных графов. Для данного класса графов проблема проверки изоморфизма представляется потенциально сложной. Предложенный в работе подход, возможно, позволит обобщить полученные результаты.

теория графов, графы Деза, кореберно-регулярные графы, графы с несвязной второй окрестностью, изоморфизм графов.

1. Гаврилюк А. Л., Горяинов С. В., Кабанов В. В. О вершинной связности графов Деза // Тр. Ин-та математики и механики УрО РАН. Екатеринбург, 2013. Т. 19, № 3. C. 94–104.

2. Гаврилюк А. Л., Шалагинов Л. В. О графах Деза с 4-мя различными собственными значениями //Тезисы Международной (43-й Всероссийской) молодежной школы-конференции. Екатеринбург, 2012. C. 20–23.

3. Erickson M., Fernando S., Haemers W. H., Hardy D. and Hemmeter J. Deza graphs: a generalization of strongly regular graphs // J. Comb. Designs. 1999. Vol. 7, P. 359–405.

4. Ермакова Г. М. Две задачи алгебраической теории графов // Автореферат диссертации на соискание ученой степени кандидата ф.-м. н., УрО РАН, Екатеринбург, 2009.

5. Кабанов В. В., Митянина А. В. Реберные точные графы Деза // Тр. ИММ УрО РАН, 18:1 (2012), 165–177.