Читать онлайн «О сильно регулярных локально GQ(4,t) графах»

Сибирский математический журнал Январь—февраль, 2008. Том 49, № 1 УДК 519. 14 О СИЛЬНО РЕГУЛЯРНЫХ ЛОКАЛЬНО GQ(4, t) ГРАФАХ А. А. Махнев Аннотация. Неориентированный v-вершинный граф, в котором степени всех вер- шин равны k, каждое ребро принадлежит λ треугольникам и пересечение окрест- ностей любых двух вершин, находящихся на расстоянии 2, содержит µ вершин, на- зывается вполне регулярным с параметрами (v, k, λ, µ). Вполне регулярный граф диаметра 2 называется сильно регулярным. Доказано несуществование вполне ре- гулярных локально GQ(4, t) графов для (t, µ) = (4, 10) и (8,30). Тем самым про- блема классификации сильно регулярных локально GQ(4, t) графов редуцирована к изучению локально GQ(4, 6) графов с параметрами (726,125,28,20). Ключевые слова: сильно регулярный граф, обобщенный четырехугольник, ги- перовал. Введение Мы рассматриваем неориентированные графы без петель и кратных ре- бер. Для вершины a графа € через €i (a) обозначим i-окрестность вершины a, т. е. подграф, индуцированный € на множестве всех вершин, находящихся на расстоянии i от a. Положим € (a) = €1 (a), a⊥ = {a} ∪ € (a). Если граф € зафик- сирован, то вместо € (a) T будем писать [a]. Для множества вершин X графа € через X ⊥ обозначим x⊥ . Если не оговорено иное, то слово «подграф» будет x∈X означать «индуцированный подграф». Пусть F — некоторый класс графов. Граф € назовем локально F графом, если [a] лежит в F для любой вершины a графа € . Если при этом класс со-F стоит из графов, изоморфных некоторому графу , то граф € назовем локально  графом. Пусть € — граф, a, b ∈ € , число вершин в [a] ∩ [b] обозначается через µ(a, b) (через λ(a, b)), если a, b находятся на расстоянии 2 (смежны) в € . Далее, инду- цированный [a] ∩ [b] подграф называется µ-подграфом (λ-подграфом). Степенью вершины называется число вершин в ее окрестности. Граф € называется регулярным степени k, если степень любой вершины a из € равна k. Граф € назовем реберно регулярным с параметрами (v, k, λ), если он содержит v вершин, регулярен степени k и каждое его ребро лежит в λ треугольниках. Граф € — вполне регулярный граф с параметрами (v, k, λ, µ), если он реберно регулярен c соответствующими параметрами и [a] ∩ [b] содержит µ вершин для Работа выполнена при финансовой поддержке Российского фонда фундаментальных ис- следований (код проекта 05–01–00046), РФФИ–ГФЕН Китая (грант 05–01–39000), программы отделения математических наук РАН и программы совместных исследований с Сибирским отделением РАН. c 2008 Махнев А. А. 162 А. А. Махнев любых двух вершин a, b, находящихся на расстоянии 2 в € . Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.