Инфоурок / Математика / Другие методич. материалы / О ГРАФАХ, В КОТОРЫХ ОКРЕСТНОСТИ ВЕРШИН СИЛЬНО РЕГУЛЯРНЫ С ПАРАМЕТРАМИ (111, 30, 5, 9) ИЛИ (169, 42, 5, 12)

О ГРАФАХ, В КОТОРЫХ ОКРЕСТНОСТИ ВЕРШИН СИЛЬНО РЕГУЛЯРНЫ С ПАРАМЕТРАМИ (111, 30, 5, 9) ИЛИ (169, 42, 5, 12)

Напоминаем, что в соответствии с профстандартом педагога (утверждён Приказом Минтруда России), если у Вас нет соответствующего преподаваемому предмету образования, то Вам необходимо пройти профессиональную переподготовку по профилю педагогической деятельности. Сделать это Вы можете дистанционно на сайте проекта "Инфоурок" и получить диплом с присвоением квалификации уже через 2 месяца!

Только сейчас действует СКИДКА 50% для всех педагогов на все 111 курсов профессиональной переподготовки! Доступна рассрочка с первым взносом всего 10%, при этом цена курса не увеличивается из-за использования рассрочки!

ВЫБРАТЬ КУРС И ПОДАТЬ ЗАЯВКУ

Краткое описание документа:

О ГРАФАХ, В КОТОРЫХ ОКРЕСТНОСТИ ВЕРШИН СИЛЬНО РЕГУЛЯРНЫ С ПАРАМЕТРАМИ (111, 30, 5, 9) ИЛИ (169, 42, 5, 12) А.М. КАГАЗЕЖЕВА, А.А. МАХНЕВ В [1] начато решение задачи изучения графов, в которых окрестности вершин — сильно регулярные графы с неглавным собственным значением 3. А именно, получена редукция задачи к изучению графов, в которых окрестности вершин являются исключительными сильно регулярными графами с неглавным собственным значением 3. В [2] найдены пара- метры исключительных сильно регулярных графов с неглавным собственным значением 3. В частности, граф с λ = 5 имеет параметры (21, 10, 5, 4), (111, 30, 5, 9) или (169, 42, 5, 12). В данной работе изучены вполне регулярные графы, в которых окрестности вершин сильно регулярны с указанными параметрами. Теорема 1. Пусть Γ — вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы с параметрами (111, 30, 5, 9), u — вершина графа Γ и ki = |Γi(u)|. Тогда d(Γ) = 3, k3 четно и выполняется одно из утверждений: (1) µ = 30, 2 ≤ k3 ≤ 18; (2) µ = 40, 2 ≤ k3 ≤ 6 и Γ3 является объединением изолированных вершин и ребер. Теорема 2. Пусть Γ — вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы с параметрами (169, 42, 5, 12), u — вершина графа Γ и ki = |Γi(u)|. Тогда d(Γ) = 3 и выполняется одно из утверждений: (1) µ = 39, k3 четно, 2 ≤ k3 ≤ 42; (1) µ = 42, k3 нечетно, 3 ≤ k3 ≤ 33 (3) µ = 63, k3 четно, 2 ≤ k3 ≤ 12 и Γ3 является объединением изолированных вершин и ребер. Следствие. Пусть Γ — дистанционно регулярный граф, в котором окрестности вершин — сильно регулярные графы с собственным значением 3 и параметрами (v 0 , k0 , 5, µ0 ). Тогда окрестности вершин либо изоморфны треугольному графу T(7) и Γ — половинный граф 7-куба, либо сильно регулярны с параметрами (169, 42, 5, 12) и Γ имеет массив пересечений {169, 126, 1; 1, 42, 169}. Работа выполнена при поддержке РФФИ (грант 12-01-00012), программы отделения математических наук РАН (проект 12-T-1-1003) и программ совместных исследований УрО РАН с СО РАН (проект 12-С-1-1018) и с НАН Беларуси (проект 12-С-1-1009). Список литературы [1] Махнев А.А. О сильно регулярных графах с собственным значением 3 и их расши- рениях. Доклады академии наук. 451:5, 2013, С. 475–478. [2] Махнев А.А., Падучих Д.В. Исключительные сильно регулярные графы с собствен- ным значением 3 и их расширения. Межд. конф. "Алгебра и комбинаторика". Тез. докл. Екатеринбург, 2013, С. 67-69. Институт математики и механики им. Н.Н. Красовского УрО РАН, Екатеринбург (Рос- сия) E-mail address: makhnev@imm.uran.ru 1

Общая информация

Номер материала: 389636

Похожие материалы