Читать онлайн «Об автоморфизмах графа Ашбахера»

Алгебра и логика, 40, N 2 (2001), 125-134 УДК 519. 14+512. 542 ОБ А В Т О М О Р Ф И З М А Х ГРАФА АШБАХЕРА*) А. А. МАХНЕВ, Д . В. П А Д У Ч И Х В настоящей статье рассматриваются неориентированные графы без петель и кратных ребер. Для вершины а графа Г через [а] обозначается окрестность вершины а, т. е. подграф, индуцированный Г на множестве всех смежных с а вершин. Положим ах — {a} U [а]. Граф называется сильным с параметрами (А,/х), если любое его реб­ ро лежит в Л треугольниках, и любая пара несмежных вершин имеет \х общих соседей. Граф Г называется сильно регулярным с параметрами (u,fc, А,/х), если он имеет v вершин, регулярен валентности к и являет­ ся сильным с соответствующими параметрами. Звездой называется граф, содержащий такую вершину а, что любая отличная от а вершина графа смежна только с а. Если звезда имеет не менее трех вершин, то а назовем централь звезды. Если регулярный граф валентности к диаметра d имеет v вершин, то выполняется неравенство, доказанное Муром (см. [1]): v <$ 1 + к + к{к - 1) + • • • + к(к - l)d~\ Графы, для которых это нестрогое неравенство превращается в равен­ ство, называют графами Afypa. Они имеют нечетный обхват, равный 2d+l. Синглтон [2] установил, что связный граф диаметра d и обхвата 2d+ 1 яв­ ляется графом Мура. Интересно, что графы Мура будут экстремальными и относительно нижней оценки для числа вершин. А именно, число вершин *> Работа выполнена при финансовой поддержке Российского фонда фундаменталь­ ных исследований, проект N 99-01-00462* © Сибирский фонд алгебры и логики, 2001 126 А. А. Махнев, Д. В. Падучих v регулярного графа валентности к и нечетного обхвата g удовлетворяет неравенству v J> 1 + к + к{к - 1) + • • • + к{к - 1)(з~ 3 )/ 2 . Графы, для которых достигается равенство, являются графами Мура. Простейший пример графа Мура доставляет (2d+ 1)-угольник. Дамерелл [3] доказал, что граф Мура валентности к ^ 3 имеет диаметр 2. В этом случае v = к2 + 1, граф сильно регулярен сА = 0 и / х = 1,а валентность к равна 3 (граф Петерсена), 7 (граф Хоффмана—Синглтона) или 57. Пер­ вые два графа являются графами ранга 3 с группами автоморфизмов S$ и Us(5)(x) соответственно, где х индуцирует полевой автоморфизм на U$(b). Существование графа Мура валентности к = 57 неизвестно. Ашбахер [4] доказал, что граф Мура с к — 57 не является графом ранга 3. Мы будем называть граф Мура с к = 57 графом Ашбахера. Камерон [5] доказал, что граф Ашбахера не может быть вершинно транзитивным. Цель данной работы — получение информации о строении группы автоморфизмов гипотетического графа Ашбахера. Если X — некоторое множество автоморфизмов графа Г, то через Fix(X) обозначим множество всех вершин из Г, неподвижных относительно любого автоморфизма из X. Т Е О Р Е М А . Пусть Г — граф Ашбахера, G = Aut(F). Предполо- эюим, что G содержит инволюцию t. Тогда выполняю7пся следующие утверждения: (1) Fix(£) является звездой, содержащей 56 вершищ (2) G — Y(t) х X для некоторых подгрупп Х) Y нечетного порядка, Y инвертируется t и либо \Y\ делит 5 или 57, либо \Y\ делит 21 (в случае \Y\ = 21 имеем |Fix(y)| = 37 для элемента у порядка 7 из У); (3) если X ф I, то Fix(X) — либо звезда, Y — 1, \Х\ = 7; либо пятиугольник, \Y\ делит 5, \Х\ делит 55; либо граф Петерсена, \Y\ делит 3, \Х\ делит 27; либо граф Хоффмана—Синглтона, \Y\ делит 5 или 7, \Х\ делит 25.