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

• Токбаева, Альбина Аниуаровна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Токбаева, Альбина Аниуаровна

Введение

1 Реберно регулярные графы с к — Збх —

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

1.2 Хорошие пары вершин в графах с к = 3^1 — 2.

1.3 Оценка для числа вершин в графах с к = 3Ь\ —

2 Автоморфизмы графов с параметрами (76, 35.18,14)

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

2.2 Автоморфизмы графа с параметрами (76,35,18,14).

3 Автоморфизмы графа с параметрами (243,66,9,21)

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

3.2 Автоморфизмы графа с параметрами (243,66,9,21).

3.3 Автоморфизмы малых порядков.

3.4 Реберно симметричный случай.

Введение диссертации (часть автореферата) на тему «Почти хорошие тройки вершин в графах и автоморфизмы графов»

Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию ([23], [24], [36], [21]). Например, класс билдингов Титса характеризует группы лиева типа [40]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [20].

Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах XX века. Пусть Ь(Кп) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т{п). Этот граф является сильно регулярным графом с параметрами (п(п — 1)/2, 2{п — 2),п — 2,4). В работах 1959-60 годов Л. Чанг [28] и А. Хоффман ([33], [34]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п — 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [27].

Реберный граф Ь(Кт^п) полного многодольного графа Кт>п является ко-реберно регулярным графом с параметрами (тп,т + п —2,2). Граф Ь(Кт:Т1) называют т х п-решеткой. При т — п решетчатый граф является сильно регулярным графом с параметрами (п2,2п — 2, п — 2, 2). С. Шрикханде в [38] показал, что граф, имеющий параметры п х п решетки является либо решеткой, либо графом Шрикханде (п — 4).

Результаты Л. Чанга, С. Шрикханде и А. Хоффмана [35] были объединены Дж. Зейделем [37], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п х п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы КпХ2, графы Пстерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через с?(а, 6) обозначается расстояние между а и 6, а через Гг(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.

Подграф Гх(а) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.

Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.

Граф Г называется реберно регулярным графом с параметрами {у, к, А), если Г содержит V вершин, является регулярным степени /с, и каждое ребро из Г лежит в Л треугольниках.

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

Число вершин в [а] П [6] обозначим через Л(а, 6), если с1(а,Ь) = 1, а соответствующий подграф назовем \-подграфом.

Если с?(а, Ь) = 2, то число вершин в [а] П [6] обозначим через //(а, 6), а соответствующий подграф назовем ¡л-подграфом.

Если вершины и,ии находятся на расстоянии г в Г, то через ги) (через Сг(и, ии)) обозначим число вершин в пересечении Г,;+1 (и) (Ггх(г«)) с Г(т). Заметим, что в реберно регулярном графе число Ъ\{и^) не зависит от выбора смежных вершин и,ни и равно Ъ\ = к — А — 1.Граф Г диаметра с1 называется дистанционно регулярным с массивом пересечений {&о> Ьь ■ ■ •, Ьа-1, Сх,., со}, если значения Ь{(и, ги) и С((и, ги) не зависят от выбора вершин и,т на расстоянии г в Г для любого г = 0,

Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально А-графом.

Пусть Г — реберно регулярный граф с параметрами (у, к, А) и Ъ\ = к—А—1. Пара вершин и,и> называется (почти) хорошей, если б1{и,ш) — 2 и ¡¿(и,ги) равно к — 26х + 1 (равно к — 2Ьг + 2). Тройка вершин (и,ги,г) называется (почти) хорошей, если ии, г е Г2(и) и [¿(и, ги) + дл(гл, г) не больше 2к — 4Ъ\ + 3 (равно 2к - 4&1 + 4).

Основанием для развития метода хороших пар стало следующее наблюдение. Пусть Г — реберно регулярный граф с параметрами (и, к, А) и 61 = к — Л — 1. Если вершины и, ш находятся на расстоянии 2 в Г, то выполняются следующие утверждения:

1) степень любой вершины в /1-подграфе из Г не меньше к — 2Ьу,

2) вершина (I имеет степень а в графе [и] П [ги], тогда и только тогда, когда [с1] содержит точно а — {к — 2Ъ\) вершин вне и1- и ги1-]

3) если /1(и,ги) = к — 2Ъ\ + 1, то подграф [и] П [ги] является кликой и Щ С и1 и и)1- для любой вершины с1 Е [и] П [ги];

4) если Г — (и1- U г/г1) содержит единственную вершину z, то ц(и, z) — ß{w,z).

A.A. Махнев [1] получил следующее свойство хороших троек:

Пусть Г — реберно регулярный граф, содержащий хорошую тройку (u, w, z) и 8 = \[и] П И П [z]|. Тогда выполняются следующие утверждения:

1) если fi(u, w) = fi(u, z) = к — 2Ь\ + 1, то 6 = 0 в случае, когда вершины w, z не смежны и 6 < 1 в случае, когда вершины w, z смежны;

2) если ¡¿(и, w) + fi(u, w) = 2к — 4&i + 3, то 5 < 1.

С помощью этих результатов получается новое доказательство классификации графов Тсрвиллигера без 3-лап. Получение аналогичных оценок для почти хороших троек потребовало значительных усилий (см. [2] — [5]). В [6]) была доказана

Теорема А. Пусть Г — связный реберно регулярный граф с параметрами (v,k,X), к = 36i + 7 и 7 > —2. Если (u,w,z) — почти хорошая тройка и А = [и] П [w] П [z] — непустой граф, то вершины w, z смежны и выполняется одно из следующих утверждений:

1) |Д| < 2 и 7 < —1;

2) подграф Д является 3-кликой, 6i = 6, к = 16 и v = 31;

3) подграф Д является 3-кликой, Ьу = 3 и Г — граф Клебша;

4) подграф А является А-кликой, Ъ\ = 5 и Г — граф Шлефли.

С помощью теоремы А были найдены новые верхние границы для числа вершин реберно регулярных графов (в случае k > 36i Исаковой М.М., в случае к — 3bi — 1 Чуксиной Н.В. и в случае к = 3&i — 2 Токбаевой A.A.).

Цель диссертации. Целью данной работы является решение следующих задач:

1. Найти новые верхние границы для числа вершин реберно регулярных графов с к = 3&1 — 2.

2. Найти возможные порядки и подграфы неподвижных точек сильно регулярного графа с параметрами (76,35,18,14).

3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (243,66,9,21).

Методы исследования. Основными методами исследования являются методы теории конечных групп, теории характеров, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.

Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие.

1. Найдены новые верхние оценки для числа вершин реберно регулярных графов с к = Збх — 2.

2. Определены возможные порядки элементов группы С автоморфизмов сильно регулярного графа с параметрами (76,35,18,14), в частности, установлено, что тг(С) С {2,3,5,7,19}.

3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (243,66,9,21). Доказано, что граф Г не является реберно симметричным.

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

Апробация работы. Основные результаты работы докладывались на:

Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2009-2010 гг.) и на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения В.А. Белоногова (Нальчик, 2010 г.).

Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН и Кабардино-Балкарского госуниверситета.

Публикации. Основные результаты диссертации опубликованы в работах [41]-[47]. Работы [41]-[46] выполнены в нераздельном соавторстве с A.A. Мах-невым.

Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 47 наименований. Объем диссертации — 91 стр.

Список литературы диссертационного исследования кандидат физико-математических наук Токбаева, Альбина Аниуаровна, 2010 год

1. Махнев, А.А.О хороших парах в реберно регулярных графах/ A.A. Мах-нев, A.A. Веденев, А.Н. Кузнецов, В.В. Носов // Дискрет. матем.-2003.-Т.15.- С.77-97.

2. Махнев, A.A. О хороших парах вершин в графах с к > 3&i — 2 / A.A. Махнев, И.М. Минакова// Труды Междунар. конф. "Алгебра и линейная оптимизация". Екатеринбург, 2002 С. 172-1'74.

3. Белоусов, И.Н. О почти хороших парах вершин в реберно регулярных графах / И.Н. Белоусов, A.A. Махнев // Известия Уральского госуниверситета.- 2005.- Т. 36, № 7.- С.35-48.

4. Махнев A.A. О реберно регулярных графах, не содержащих хороших пар / A.A. Махнев, A.C. Омельченко // Известия Гомельского госун-та.-2008.- Т. 47. С. 117-127.

5. Махнев, A.A. О реберно регулярных графах, в которых каждая вершина лежит не более чем в одной хорошей паре / A.A. Махнев, Н.В. Чуксина // Владикавказский матем. журнал.- 2008.- Т. 10, № 1,- С. 53-67.

6. Махнев A.A. О почти хороших тройках вершин в реберно регулярных графах / В.И. Казарина, A.A. Махнев // X Белорусская матем. конф. Тез. докл. Минск,- 2008,- С. 46.

7. Махнев, A.A. О сильно регулярных графах с к = 2/i и их пасширениях /A.A. Махнев // Сиб. матем. журнал,- 2002,- Т. 43, № 3.- С. 609-619.

8. Махнев, A.A. Об автоморфизмах сильно регулярного графа с параметрами (95,40,12,20) / A.A. Махнев, Н.В. Чуксина // Владикавказский матем. журнал,- 2009.- Т. И, № 4.- С. 44-58.

9. Махнев, A.A. Об автоморфизмах графа Ашбахера/ A.A. Махнев, Д.В. Падучих // Алгебра и логика,- 2001,- Т.40, № 2.- С. 125-134.

10. Махнев, A.A. Об автоморфизмах сильно регулярных графов с Л = 0, ¡1 = 2/ A.A. Махнев, В.В. Носов// Мат. сб.- 2004,- Т.185, № 3.- С. 47-68.

11. Махнев, A.A. Об автоморфизмах графов сА = 1,/л = 2/ A.A. Махнев, И.М. Минакова // Дискрет, матем,- 2004,- Т.16, № 1,- С. 95-104.

12. Белоусов И.Н. О сильно регулярных графах с ¡i = 1 и их автоморфизмах / И.Н. Белоусов, A.A. Махнев // Доклады Академии Наук.- 2006.- Т. 410, № 2,- С. 151-155.

13. Махнев, A.A. О расширениях частичных геометрий, содержащих малые /i-подграфы /A.A. Махнев // Дискр. анализ и исслед. операций,- 1996-Т.З.- С.71-83.

14. Махнев, A.A. О сильной регулярности некоторых реберно регулярных графов / A.A. Махнев // Известия РАН, сер. матем,- 2004,- Т.68.- С. 159172.

15. Махнев A.A. О несуществовании сильно регулярных графов с параметрами (486,165,36,66) / A.A. Махнев // Украинский матем. журнал.- 2002.Т. 54, № 7.- С. 941-949.

16. Махнев А.А. Об одном классе реберно регулярных графов / А.А. Мах-нев, И.М. Минакова // Известия Гомельского госуниверситета, Вопросы алгебры,- 2000,- Т. 3 (16).- С. 145-154.

17. Журтов А.Х. Об автоморфизмах 4-изорегулярных графов / А.Х. Жур-тов, А.А. Махнев, М.С. Нирова //8 Международная школа-конференция по теории групп. Нальчик 2010. Тез. докл.- С. 94-102.

18. Кондратьев, А.С. Распознавание знакопеременных групп простой степени / А.С. Кондратьев, В.Д. Мазуров // Сиб. матем. ж,- 2000.- Т. 41, № 2.- С.359-369.

19. Падучих Д.В. Новая оценка для число вершин реберно регулярных графов / А.А. Махнев, Д.В. Падучих // Сибирский матем. журнал,- 2007.Т. 48, № 4,- С. 817-832.

20. Brouwer, А.Е. Distance-regular graphs/ А.Е. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag.- 1989.- 495 c.

21. Brouwer, A.E. Block designs/ A.E. Brouwer, H.A. Willbrink// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsever Science. Amsterdam.- 1995.- P.349-383.

22. Brouwer, A.E. The Gewirtz graph: an exercize in the theory of graph spectra/ A.E. Brouwer, W.H. Haemers// Europ. J. Comb.- 1993.- Vol.14.- P.397-407.

23. Buekenhout, F. Foundations of incidence geometry / F. Buekenhout// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsever Science. Amsterdam.- 1995 - P.63-107.

24. Buekenhout, F. Finite diagram geometries extending buildings/ F. Buekenhout, P. Pasini// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout.— Elsever Science. Amsterdam.- 1995.- P. 11431255.

25. Cameron, P. Permutation Groups/ P. Cameron.- London Math. Soc. Student Texts 45.: Cambridge Univ. Press, 1999.

26. Cameron, P. J. Graphs, Codes and Desidns. / Cameron P. J., van Lint J.London Math. Soc., Student Texts №22, Cambridge: Cambridge Univ. Press, 1991.

27. Chang, L.C. The uniqueness and nonuniqueness of triangular association schemes/ L.C. Chang// Sci. Record.- 1949,- Vol.3.- P.604-613.

28. Chang, L.C. Association schemes of partially balanced block designs with parameters v = 28,n\ = 12,n0 = 15 andp2 = 4/ L.C. Chang// Sci. Record-1950,- Vol.4.- P.12-18.

29. Gardiner A. Homogeneous graphs / A.Gardiner //J. Comb. Theory.- 1976.-V. 20.- P. 94-102.

30. Guralnik R.M. Subgroups of prime power index in a simple group / R.M. Guralnik // J. Algebra.- 1983.- V. 81, № 2,- P. 304-311.

31. Hoffman, A.J. On the uniqueness of the triangular association scheme/ A.J. Hoffman// Ann. Math. Stat.- I960.- Vol.31.- P.492-497.

32. Hoffman, A.J. On the exceptioal case in a characterization of the arcs of complete graphs/A.J. Hoffman// IBM J. Res. Develop.- I960,- Vol.4.- P.487-496.

33. Hoffman, A.J. On the line-graphs of the complete bipartite graph/ A.J. Hoffman// Ann. Math. Stat.- 1964,- Vol.35.- P.883-885.

34. Prager, C.E. Low rank representations and graphs for sporadic groups/ C.E. Prager, L.H. Soicher.- Lecture series 8,- Cambridge: University press.-1997.

35. Seidel, J.J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3/ J.J. Seidel// Linear Algebra and Appl.- 1968.- Vol.1.- P.281-298.

36. Shrickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhande// Ann. Math. Stat.- 1959,- Vol.30.- P.781-798.

37. Macay M. Search for properties of the missing Moore graph / M. Macay, J. Siran // Linear Algebra and its Appl.- 2009.- V. 432.- P. 2381-2398.

38. Tits, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.Работы автора по теме диссертации

39. Токбаева А.А. О числе вершин в реберно регулярных графах с к — 36i — 2 / А.А. Махнев, А.А. Токбаева // Труды 40-й Вссросс. молод, конф. Изд-во ИММ УрО РАН: Екатеринбург.- 2009.- С. 32-35.

40. Токбаева A.A. О числе вершин в реберно регулярных графах с к = 3bi — 2 / A.A. Махнев, A.A. Токбаева // Алгебра и ее приложения. Труды межд. конф., посвященной 80-летию со дня рождения А.И. Кострикина. КБГУ: Нальчик,- 2009. С. 87-91.

41. Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (76,35,18,14) / A.A. Махнев, A.A. Токбаева // Тезисы 41-й Всеросс. молод, конф. Изд-во МММ УрО РАН: Екатеринбург.- 2010.- С. 42-46.

42. Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (243,66,9,21) / A.A. Махнев, A.A. Токбаева // Теория групп и ее приложения. Труды межд. конф., посвященной 75-летию со дня рождения В.А. Белоногова. КБГУ: Нальчик,- 2009,- С. 89-93.

43. Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (76,35,18,14) / М.М. Исакова, A.A. Махнев // Труды ИММ УрО РАН,- 2010.- Т. 16, № 3.- С. 186-195.

44. Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (243,66,9,21) / A.A. Махнев, A.A. Токбаева // Владикавказский матем. журнал,- 2010.- Т. 12, № 4,- С.

45. Токбаева A.A. Сильно регулярный граф с параметрами (243,66,9,21) не является реберно симметричным / A.A. Токбаева // Сибирские электронные матем. известия,- 2010,- Т. 7.- С. 155-161.