Читать онлайн «О сильно регулярных графах с k=2i и их расширениях»

Сибирский математический журнал Май—июнь, 2002. Том 43, № 3 УДК 519. 14 О СИЛЬНО РЕГУЛЯРНЫХ ГРАФАХ С k = 2µ И ИХ РАСШИРЕНИЯХ А. А. Махнев Аннотация: Получено удобное выражение параметров сильно регулярного графа с k = 2µ через неглавные собственные значения x, −y. Оказалось, в частности, что такие графы являются псевдогеометрическими для pGx (2x, y − 1). Доказано, что сильно регулярный граф с параметрами (35, 16, 6, 8) является частным графа Джонсона J(8, 4). Далее, найдены параметры сильно регулярных графов, в кото- рых окрестности вершин являются псевдогеометрическими графами для pGx (2x, t), x ≤ 3. Как следствие установлено, что связный граф, в котором окрестности вершин являются псевдогеометрическими графами для pG3 (6, 2), совпадает с гра- фом Тэйлора или графом знакопеременных форм Alt(4, 2), имеющим параметры (64, 35, 18, 20). Библиогр. 8. Мы рассматриваем неориентированные графы без петель и кратных ребер. Если a, b — вершины графа Γ, то через d(a, b) обозначается расстояние между a и b, а через Γi (a) — подграф графа Γ, индуцированный множеством вершин, которые находятся в Γ на расстоянии i от вершины a. Подграф Γ1 (a) называ- ется окрестностью вершины a и обозначается через [a]. Через a⊥ обозначается подграф, являющийся шаром радиуса 1 с центром a. Граф Γ называется регулярным графом степени k, если [a] содержит точно k вершин для любой вершины a из Γ. Граф Γ называется реберно регулярным графом с параметрами (v, k, λ), если Γ содержит v вершин, является регуляр- ным степени k и каждое ребро в Γ лежит в λ треугольниках. Граф Γ называется вполне регулярным графом с параметрами (v, k, λ, µ), если Γ реберно регуля- рен с соответствующими параметрами и подграф [a] ∩ [b] содержит µ вершин в случае d(a, b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Число вершин в [a] ∩ [b] обозначим через λ(a, b) (через µ(a, b)), если d(a, b) = 1 (если d(a, b) = 2), а соответствующий подграф назовем (µ-) λ-подграфом. Треугольным графом T (m) называется граф с множеством неупорядочен- ных пар из X в качестве вершин, при этом |X| = m и пары {a, b}, {c, d} смежны тогда и только тогда, когда они имеют единственный общий элемент. Граф на множестве вершин X × Y называется m × n решеткой, если |X| = m, |Y | = n и вершины (x1 , y1 ), (x2 , y2 ) смежны тогда и только тогда, когда x1 = x2 или y1 = y2 . Дистанционно регулярный граф Γ диаметра d называется антипо- дальным, если отношение «совпадать или находиться на расстоянии d» являет- ся отношением эквивалентности на множестве вершин графа. Если r — число вершин в каждом классе эквивалентности, то Γ называется r-антиподальным Работа выполнена при финансовой поддержке Российского фонда фундаментальных ис- следований (код проекта 99–01–00462). c 2002 Махнев А. А. 610 А.