Автоморфизмы и локальная структура графов тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Падучих, Дмитрий Викторович

• Падучих, Дмитрий Викторович
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Падучих, Дмитрий Викторович

1. Влияние 2-окрестностей на строение графа

2. 2-Локально графы Зейделя

2.1. Редукция к графам диаметра 2.

2.2. 2-локально решетчатые графы.

2.3. Треугольные графы и графы Чанга.

2.4. Графы Петерсена, Шлефли и Шрикханде.,

2.5. Граф Клебша.

3. Локально Шрикханде графы и их автоморфизмы

3.1. Вспомогательные результаты

3.2. Несвязные /¿-подграфы.

3.3. Связные /2-подграфы

4. Классификация локально 3,9) графов

4.1. Предварительные результаты.•.

4.2. Гиперовалы в вС}(3,9).

4.3. Локально 0(^(3,9) графы.

5. Автоморфизмы графов Мура

Введение диссертации (часть автореферата) на тему «Автоморфизмы и локальная структура графов»

Основные определения. Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ь — вершины графа Г, то через с?(а, Ъ)• обозначим расстояние между а и 6, а через Гг(а) — подграф,,индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии г от вершины а. Подграф Г'1(а) будем называть окрестностью вершины а и обозначать через [а], если понятно о каком графе идет речь. Через а1 обозначим подграф, индуцированный {а} и [а], а через [а]' — подграф Г - а1.

Валентностью вершины называется число вершин в ее окрестности. Граф Г называется регулярным валентности к\ если валентность любой вершины а из Г равна к. Граф Г назовем реберно регулярным (кореберно регулярным) с параметрами '(у, к, А) (с параметрами (у, к,-¡л)), если он содержит у вершин, регулярен валентности к, и каждое его ребро аЬ лежит в А треугольниках (любые две несмежные вершины а, Ь имеют /л общих соседей). Подграф, индуцированный на (а] П [Ь], назовем (Л-) /^-подграфом, если вершины а,Ь (смежны) находятся на расстоянии 2.

Граф Г — вполне регулярный граф с параметрами (г>, к, Л, /л), если он реберно регулярен с соответствующими параметрами и [а] П [6] содержит ¡л вершин для любых двух вершин а, 6, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.

Назовем дистанционно регулярным графом с массивом пересечений регулярный связный граф диаметра й такой, что для любой пары вершин (я, у), находящихся на расстоянии верны равенства

Г;!(у) П Г1(®)| = Ф < 3 < ¿0,|Г,-+1 {у) П Гх(х)| = ЬДО <3<с1- 1).

Легко понять, что для любого дистанционно регулярного графа верны равенства &о — к и с\ = 1.

Дистанционно регулярный граф диаметра в, называется антипо-далъным, если уравнение с1(х, у) = й задает отношение эквивалентности на множестве вершин графа. Графом Тэйлора называется ди-' станционно регулярный граф с массивом пересечений {к, ¡л,к}.

Легко понять, чтограф Тэйлора антиподален с классами эквивалентности порядка 2.

Для подграфа А графа Г через К{(А) обозначим множество вершин из Г — А, смежных с % вершинами из А, жг-(А) = |А'г(А)|.

Постановка задачи. Результаты, полученные в данной диссертации, имеют своей целью исследование графов с ограничением на локальную структуру. Постановка задачи описания графов с ограничением на локальную структуру происходит от аналогичной задачи для конечных геометрий. Мы приведем в связи с этим определение геометрии ранга п, принадлежащее Титсу [27].

Определение. Пусть I — конечное множество. Геометрия ранга п над I — это тройка Я = (X, где X — множество объектов; t — типовая функция, отображающая X в I (сопоставляющая объекту из X его тип), такая что Х)| = п; и * — рефлексивное симметричное отношение инцидентности на X, причем объекты одного типа а, Ъ инцидентны, только если а = Ь.

Флагом геометрии Я называется набор попарно инцидентных объектов. Типом флага Г называется множество рангом флага Р — число

Вычет Яр флага Г геометрии Я — это множество объектов X? = {и € X — ¥| и * / для всех / € рассмотренное как геометрия над I — Каждый вычет геометрии сам является геометрией.

Особую роль играют геометрии ранга 2 — каждой геометрии Я можно сопоставить семейство геометрий Яц ранга 2 (г,] € I, г ф /), являющихся вычетами флагов типа Обратно, можно поставить задачу описания класса геометрий Я при заданном семействе Яц- Исторически подобные исследования появились в работах Титса [26], [27] с целью описания групп Шевалле как групп автоморфизмов геометрий определенного класса (билдингов). В общем случае эта задача была впоследствии сформулирована Бюкенхаутом [14].

Чтобы установить связь между геометриями и графами в этом контексте, следует рассмотреть геометрии ранга 2 более подробно. Говоря о геометриях ранга 2 не вполне удобно пользоваться общим определением геометрии, поэтому обычно формулируется следующий упрощенный его вариант.

Определение. Геометрия 0 ранга 2 — это пара (Р,В), где Р — некоторое множество точек, а В — система его подмножеств, называемых блоками. Множество точек, колинеарных точке х (т. е. лежащих с ней в одном блоке), будем обозначать через х1-.

Вычетом геометрии 0 в точке х называется геометрия 0Х — (.РХ,ВХ), где Р^х1-- {х}, Вх = {Ь - {х} | I е В,1 Э х}.

Отметим, что в этом случае имеется точно два типа объектов — "точка" и "блок", а отношение * — это симметризованное включение.

Определение. Расширением семейства 5 геометрий ранга 2 называется геометрия 0, такая что вычет 0Х принадлежит семейству <5 для любой точки х Е Р.

Обычно задачу расширения геометрий ранга 2 решают в случае, когда <5 состоит из "хороших" геометрий. Мы введем ряд ограничений, которые понадобятся нам для дальнейшего изложения.

Пусть х£Р,ЬеВях'£Ь (пара (х, Ь) называется антифлагом). Число точек из Ь, колинеарных с х, обозначим через а(х,Ь). Геометрия 0 называется <р-однородной, если а{х,Ь) = 0 или (р для любого антифлага (х,Ь); <3 называется сильно <р-однородной, если а(х, V) = (р для любого антифлага (х, £).

Далее мы будем рассматривать только такие геометрии, в которых любые два блока пересекаются не более чем по одной точке, при этом блоки будем называть прямыми. В этом случае геометрия называется частичным линейным пространством. Геометрия называется а-частичной геометрией порядка (я, если каждая прямая содержит 5 + 1 точку, каждая точка лежит на £ +1 прямой и геометрия является сильно «-однородной (обозначение рС^я, ¿)). Двойственная геометрия к является частичной геометрией ^>GQ;(í, з).

Геометрия рО\(5, называется обобщенным четырехугольником порядка и обозначается СС}{з,{).

Любой геометрии 0 ранга 2 мы сопоставим её точечный граф

Г(£), вершинами которого являются точки из и две точки х,у смежны тогда и только тогда, когда х,у лежат в общем блоке и хф у.

Нетрудно заметить, что полученное соответствие между геометриями ранга 2 и их точечными графами не взаимооднозначно. Достаточно заметить, что точечный граф любой проективной плоскости — клика. Примером противоположной ситуации может служить а5- Если 0 = ЗДто геометрия 0 однозначно восстанавливается по своему точечному графу. Не смотря на это, задача расширения естесственным образом переносится с геометрий ранга 2 на графы.

Сформулируем задачу существования расширения на языке графов следующим образом.

Задача о расширениях на языке графов. Пусть задано семейство графов Т. Требуется определить существует ли- граф Г, окрестность каж.дой вершины которого принадлежит Т. Граф Г, удовлетворяющий данному условию, называется локально ^-графом

Задача описания локально ^-графов является классической и решена для различных классов Т (см. например [6, с. 495]).

Краткое содержание. В работе описан ряд классов графов, определяемых локальной структурой. Кроме того получены результаты о группах автоморфизмов возникающих графов.

Диссертация состоит из введения, пяти глав и списка литературы (29 наименований). Во введении обсуждается история вопроса, даются основные определения и кратко формулируются результаты работы.

Список литературы диссертационного исследования кандидат физико-математических наук Падучих, Дмитрий Викторович, 2000 год

1. Падучих Д. В. Влияние 2-окрестностей на строение графа. Мат. заметки, том 62, выпуск 6, декабрь 1997, 892-897.

2. Махнёв А.А., Падучих Д.В. О 2-локально графах Зейделя. Известия РАН, серия математическая, том 61, JNH, 1997, 67-80.

3. Махнёв А.А., Падучих Д.В. Локально Шрикханде графы и их автоморфизмы. Сиб. мат. журнал, том 39, №5, 1998, 1085-1097.

4. Махнёв А.А., Падучих Д.В. О структуре связных локально GQ(3,9)-графов. Дискретный анализ и исследование операций, серия 1, том 5, №2, 1998, 61-77.

5. Махнёв А.А., Падучих Д.В. О группах автоморфизмов частичных геометрий и их расширений. Тез. докл. // Международный алгебраический семинар. Москва, 1999. с. 41-42.

6. Brouwer А.Е., Cohen A.M., Neumaier A. Distance-Regular Graphs // Berlin etc: Springer-Verlag.- 1989.

7. Hall J.I., Shult E.E. Locally cotriangular graphs // Geom. Dedic. 1985. V. 18. №. P. 113-159.

8. Кабанов В.В., Махнёв А.А. Кореберно регулярные графы, в которых антиокрестности вершин кореберно регулярны: Тез. докл. // III Международная конференция по алгебре. Красноярск, 1993. С. 139.

9. Seidel J.J. Strongly regular graphs with (—1,1, 0) adjacency matrix having eigenvalue 3 // Lin. Alg. Appl. 1968. V. 1. №2. P. 281-298.

10. Buekenhout F., Eubaut X. Locally polar spaces and related rank 3 groups // J. Algebra. 1977. V. 45. №2. P. 391-434.

11. Махнёв А.А. О сильно регулярных графах с А = 1 // Матем. заметки. 1988. Т. 34. №5. С. 667-672.

12. Махнёв А.А. Частичные геометрии и их расширения // Успехи Мат. Наук. 1999. Т. 51. №5. С. 25-76.

13. Браувер А.Е., Линт Й.Х. ван. Сильно регулярные графы и частичные геометрии // Кибернет. сб. 1987. Т. 24. С. 186-229.

14. Buekenhout F. Diagrams for geometries and groups //J. Combin. Theory Ser. A. 1979. V. 27. P. 121-151.

15. Cuypers H., Кasikova A., Pasechnik D.V. Multiple extensions of generalized hexagons related to the simple groups McL and C03 // J. London Math. Soc. 1996. V. 54, №1. P. 16-24.

16. Махнёв А.А. Конечные локально GQ(3,3)-графы // Сиб. матем. журн. 1994. Т. 35, т. С. 1314-1324.

17. Cameron P. J., Hughes D.R., Pasini A. Extended generalized quadrangles // Geom. Dedicata. 1990. V. 35, №1-3. P. 193-228.

18. Goethals J.-M., Seidel J.J. The regular two graph on 276 points // Discrete Math. 1975. V. 12, №. P. 143-158.

19. Makhnev A.A. Locally GQ(3,5)-graphs and geometries with short lines // Всеукраинская конф. памяти П. С. Казимирского. Тез. докл. Львов 1995. С. 59-60.

20. Pasechnik D.V. The triangular extensions of a generalized quadrangle of order (3,3) // Bull. Belg. Math. Soc. 1995. V. 2. №5. P. 509518.

21. Hoffman A.J., Singleton R.R. On Moore graphs with diameters 2 and 3, IBM J. Res. Dev. 4(1960), 497-504.

22. Singleton R.R. There is no irregular Moore graph, Amer. Math. Monthly, 75(1968), 42-43.

23. Damerell R.M. On Moore graphs, Math. Proc. Cambr. Phil. Soc., 74(1973), 227-236.

24. Aschbacher M. The nonexistence of rank three permutation groups of degree 3250 and subdegree 57, J. Algebra, 19(1971), 538-540.

25. Cameron P. Permutation Groups, London Math. Soc. Student Texts 45(1999), Cambridge Univ. Press.

26. Tits J. Les groupes de Lie exceptionnels et leur interpretation geometrique // Bull. Soc. Math. Belg 1956, V. 8.- P. 48-81.

27. Tits J. Geometries polyedricues et groupes simples // Atti 2a Riunione Groupem Math. Express Lat. Firenze.- 1962, P. 66-88.

28. De Klerk F., Thas J. The embedding of (0, a)-geometries in PG{n,q). Part I // Ann. Discrete Math.- 1983, V. 18.- P. 229-240.

29. Payne S., Thas J. Finite Generalized Quadrangles.- Research Notes in Math.- 1984, V. 110.- Pitman: Boston.