Две задачи алгебраической теории графов

Пусть (7 — транзитивная группа подстановок на конечном множестве X. Если порядок группы четен, то стабилизатор в С точки х Е X имеет симметричную орбиту Д (я) на X отличную от {ж}. Тогда по группе С можно построить граф Г с множеством вершин X, и две вершины х, у смежны в Г тогда и только тогда, когда у? Д (ж).

Изучение графов, полученных. таким образом, является важной задачей алгебраической теории графов. Если в качестве группы С рассмотреть симметрическую группу подстановок 5га на п символах, а в качестве множества X — множество всех транспозиций из 5″ п и считать смежными любые две неперестановочные транспозиции, то получим треугольный граф Т{п). Нетрудно видеть, что этот граф является сильно регулярным графом с параметрами (П¹~12(п — 2), п — 2,4). Кроме того, он ие содержит порожденных подграфов В работах 1959;60 гг. Л. Чанг [10] и А. Хоффман [13], [14] независимо показали, что треугольный граф Т{п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что кроме треугольного графа Т (8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 г. [9].

Класс графов без 3-лап содержит такой важный класс графов, как реберные графы, — Реберный граф Ь (Кт^п) полного двудольного графа Кт<�п с долями порядка тип является кореберно регулярным графом с параметрами (тп, т + п — 2,2). Граф Ь{Кт^п) называют т х п-решеткой, п при т — п этот граф является сильно регулярным графом с параметрами (п2,2п — 2, п — 2,2). С. Щрикханде [18] и А. Хоффман [15] показали, что граф, имеющий параметры т х гг-решетки, является либо т х п-решеткой, либо графом Шрикханде, при п — 4. Все вышеперечисленные графы имеют наименьшее собственное значение —2. Результаты Л. Чанга, С. Шрикханде и А. Хоффмана были объединены Дж Зсйделсм [17], который определил все сильно регулярные графы с наименьшим собственным значением —2. В частности, Дж. Зейдель показал, что кроме треугольных графов Т{п) и п х n-решеток, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

Полное описание графов без 3-лап с несвязными /¿—подграфами было получено А. Брауэром и М. Нуматой [8]. Они показали, что если граф связный конечный и содержит 3-коклику, то он является m х n-решеткой Этот результат был обобщен В. В. Кабановым в [5]. Им было доказано, что связный редуцированный граф без 3-лап содержит 3-коклику, а любой его /¿—подграф имеет радиус больше 1, тогда и только тогда, когда он является либо треугольным графом Т (п) с п > 6, либо m х n-решеткой с п > 3 и m > 3, либо графом Шлефли. Граф Шлефли — это единственный сильно регулярный граф с параметрами (27,16,10,8) В работах И. А. Вакулы и В. В. Кабанова [1], [2] описаны связные графы без 3-лап с неклнковыми /¿—подграфами.

А. Деза и М. Деза рассматривали химические графы полициклнческих сопряженных углеводородов и полицикличеких ароматических углеводородов. В связи с этим исследованием возникла необходимость изучения графов, которые впоследствии были названы графами Деза.

В 1994 г. А. Деза и М Деза [11] привели пример точного графа Деза с параметрами (40,15, 6,4).

М. Эриксон, С. Фернандо, У. Х. Хаймерс, В. Харди и Дж. Хемметр [12] описали все точные графы Деза с числом вершин не более 13. A.A. Мах-невым [7] рассматривались графы Деза, которые являются кликовыми или кокликовыми расширениями сильно регулярных графов.

В диссертации рассматриваются только конечные неориентированные графы без петель и кратных ребер. Далее всюду подграф графа Г будет означать индуцированный подграф графа Г. Для вершины, а графа Г через а] ([а]') обозначим подграф на множестве всех вершин, смежных (несмежных) с а. Этот подграф называется окрестностью вершины, а в графе Г. Через ка обозначим валентность вершины, а в Г, т. е. число вершин в [а]. Граф Г называется регулярным валентности к, если ка = к для любой вершины, а из Г. Для ребра ас графа Г через Аас обозначим число вершин в подграфе [а] П [с]. Граф Г называется реберно регулярным с параметрами (г>, к, Л), если Г — регулярный граф на V вершинах валентности к, в котором каждое ребро лежит в Л треугольниках, т. е. Хас — А для любого ребра ас графа Г. Подграф [а]П[Ь] назовем ц-подграфом, ссли вершины а, Ъ находятся на расстоянии 2 друг от друга в графе Г и будем обозначать его через М (а, Ь). Граф Г на г> вершинах валентности к называется [1-регулярным с параметрами (у, к, /л), если все его д-подграфы имеют /л вершин. Если такой граф имеет диаметр 2, то он называется кореберно регулярным. Если реберно регулярный граф с параметрами (г-, к, А) является //-регулярным графом, то он называется вполне регулярным графом с параметрами (у, к, А, ¡-л). Вполне регулярный граф диаметра 2 называется сильно регулярным.

Полный граф назовем кликой, а вполне несвязный граф — кокликой. Кли-ка (коклика) порядка п называется п-кликой (кокликой).

Пусть п — натуральное число. Под п-расширением графа Г будем понимать граф Г', полученный заменой каждой вершины, а из Г на п-клику (а), причем вершины из (а) и (Ь) смежны в Г' тогда и только тогда, когда, а и Ь смежны в Г.

Графом Пэли называется граф, вершинами которого являются элементы конечного поля где д. сравнимо с 1 по модулю 4, и две вершины смежны, если разность соответствующих элементов поля Рц является ненулевым квадратом.

Граф Г на у вершинах назовем графом Деза с параметрами (у, к, Ь, а), если для любых вершин и и ги из Г.

N п N1 = { а или 6, если и ^ ги, к, если и — ги, если и — ги где V, к, Ъ, а — целые числа такие, что 0 < а <�Ь < к < V.

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

Рассмотрим графы Гх = (У^Ех) и Г2 = (Т^,^), где У и У2 — непересекающиеся множества вершин, а Е и Е2 — множества ребер графов Гх и Г2 соответственно.

Объединением таких графов Гх и Г2 назовем граф Гх и Г2 = (Ух и Уч, Е и Е2).

Суммой графов Гх и Г2 назовем граф Гх + Г2 = {У и У2, Е и Е2 и Ез), где Е3 = {{х, у} | х е Уъу € У2}.

Дополнение Г графа Г имеет в качестве множества вершин множество вершин графа Г и две вершины в Г смежны тогда и только тогда, когда они не смежны в Г.

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

1) Изучить связные графы без порожденных .К^з-подграфов, содержащих 3-коклпку, в которых для любой пары вершин и, V, находящихся на расстоянии 2 друг от друга, подграф М (и, у) — [и] П [г"] содержит /л вершин, если он не является кликой, и содержит и вершин в противном случае.

2) Исследовать точные графы Деза без’З-коклик с ¡-л = Ъ.

Методы исследования. Основными методами исследования являются методы алгебраической теории графов.

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

1. Классифицированы связные графы без порожденных /^-подграфов, содержащих 3-коклику, в которых для любой пары вершин и, v, находящихся щ, расстоянии 2 друг от друга, подграф М (и, v) = [w]n[t>] содержит? вершин, если он’не является кликой, и содержит v вершин в противном случае.

2. Найдено соотношение для параметров, а и 6 точного графа Деза без 3-коклик с il = Ъ.

3. Описаны некоторые свойства и в отдельных случаях получено полное описание точных графов Деза без 3-коклик с? = b.

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

Апробация работы. Основные результаты работы докладывались на 35-й, 37−40-ой Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2004, 2006;2009 гг.), Международной школе-конференции по теории групп (Нальчик, 2007 г.).

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

Публикации. Основные результаты диссертации опубликованы в работах [19]—[24]. Работы [19]—[22] и [24] выполнены в нераздельном соавторстве с В. В. Кабановым.

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

Результаты диссертации. Во введении обсуждается история вопроса, даются определения и формулируются основные результаты.

В главе I рассматриваются связные графы без порожденных А^з-подграфов. В. В. Кабановым, A.A. Махневым в работе [4] были классифицированы такие графы в предположении, что все /i-подграфы равномощны.

Следующий результат является основным в главе I.

Теорема 1 Пусть Г — связный граф без порожденных К^-подграфов, содержащий 3-коклику. Пусть также в Г для любой пары вершин и, v на расстоянии 2 друг от друга подграф A4 (и, v) — [и] П [г>] содержит ц вершин, если он не является кликой, и codepoicum и вершин в противном случае. Если ь> > [1, то все подграфы М (и, v) в Г одного типа, т. е. все кликовые или все неклико вые.

Из этой теоремы и результата полученного В. В. Кабановым и A.A. Мах-невым в [4] имеем.

Следствие 1 Пусть Г — связный граф без порожденных К^-подграфов, содержащий 3-коклику. Пусть таклсе в Г для любой пары вершин и, v на расстоянии 2 друг от друга подграф М{и, v) = [гг] П [г>] содержит ?1 вершин, если он не является кликой и содержит v вершин в противном случае, где и > ?1. Тогда.

1) либо граф Г является а-расширением, графа икосаэдра, либо в Г — Гх подграф на множестве всех вершин с некликовыми окрестностями является пустым графом, кликой или а-расширепием связного графа с? = 1;

2) граф Г является а-расширепием одного из следующих графов: г) т х птрешелпки, где m > 3 и п > 3- (гг) треугольного графа Т (т), т > 6- (ггг) графа Шлефли.

Во второй главе работы рассматриваются точные графы Деза без 3-коклик с ?1 = Ь. Описаны точные графы Деза, которые являются суммой сильно регулярных графов или точных графов Деза, и точные графы Деза, которые являются кликовыми расширениями сильно регулярных графов. Пусть Г — точный граф Деза без 3-коклик с ц = b и вершина х — произвольная вершина графа Г. Будем называть вершину и € [ж] графа Г вершиной «типа о» для вершины х, если [х] П |/и]| = а, а вершину ги? [ж] — вершиной «типа 6» для вершины х, если | [я] П [го] | = Ь.

Пусть у иг — несмежные вершины разных типов из [ж] и | [х] П [у] П [г] | = а. Обозначим через 5У число всех вершин, не смежных с вершиной гв [ж], а через 62 — число всех вершин, не смежных с вершиной у в [¿-с].

Если 52 = 5У + 1, то будем назвать граф Г графом типа I. Если 62 = 5У + 2, то будем назвать граф Г графом типа II.

Основными результатами второй главы являются следующие теоремы.

Теорема 2 Пусть Г — точный граф Деза с параметрами («У, к, Ь, а) без 3-коклик с ?1 — Ъ. Тогда (6 — а)? {1, 2}.

Теорема 3 Пусть Г — точный граф Деза с параметрами (1-, /г, 6, а) без 3-коклик с — Ъ и в Т есть вершина, окрестность которой содероюит две песмеэюиые вершины разных типов. Тогда.

1) если 5У = 1, то либо граф Г типа I с параметрами (8,4, 2,1) — либо Г — граф’типа II с параметрами (8 п, 8 п — 4, 8 п — 6, 8 п — 8). п > 1;

2) если, а — 5У и граф Г — граф типа I, то Г имеет параметры (8,4, 2,1) шш (12,7,4,3).

Теорема 4 Пусть Г — точный граф Деза с параметрами (и, к, Ь, а) без 3-коклик с рь = Ъ и для некоторой вершины х? Г любая вершина «типа а» смежна со всеми вершинами «типа 6», и наоборот. Если все вершины «типа 6» для х смежны между собой, то граф Г является 2-расширением графа Кп.

Теорема 5 Пусть Г — точный граф Деза с параметрами (у, к, Ь, а) без 3-коклик и Ь = а + 2. Граф Г является точный графом Деза тогда и только тогда, когда Г является вполне регулярным графом с параметрами — к -1,0, 2).

1 Графы без 3-лап.

1. Вакула, И.А. О графах без 3-лап с некликовыми /i-подграфами, натягиваемых на 3-коклику/ И. А. Вакула, В. В. Кабанов // Изв. Урал. гос. ун-та.- 2005. Т. 36. Сер. Математика и механика. Вып. 7. С. 81−92.

2. Вакула, И.А. О графах без 3-лап с некликовыми /¿—подграфами/ И. А. Вакула, В. В. Кабанов // Дискретн. анализ и исслед. опер, — Серия 1 2005.Т. 12, № 4, — С. 3−22.

3. Кабанов, В. В. Об отделимых графах с некоторыми условиями регулярности /В.В. Кабанов, A.A. Махнев // Мат. сб, — 1996. № 10. С. 73−86.

4. Кабанов, В. В. Графы без 3-лап с равномощпыми /?-подграфами/В.В. Кабанов, A.A. Махнев // Изв. Урал. гос. ун-та,.- Математика и механика-1998. № 10, — С.44−68.

5. Кабанов, В. В. Графы без 3-лап с равномощпыми /z-подграфами/ В. В. Кабанов, A.A. Махнев // Изв. Урал. гос. ун-та, — 1998. № 10- (Математика и механика. Вып.1).- С. 44−68.

6. Кабанов, В.В. О графах без корон с регулярными /¿—подграфами, II/ В. В. Кабанов, A.A. Махнев, Д. В. Падучих // Математические заметки,-2003, — Т. 74 С .396−406.

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

8. Brouwer, А.Е. A characterization of some graphs which do not contain 3-claws/A.E. Brouwer, M. Numata // Discrete Math.- 1994, — V. 124. P. 49−54.

9. Chang, L.C. The uniqueness and nonuniqueness of triangular association schemes/ L.C. Chang // Sei. Record.- 1949, — Vol. 3, — P. 604−613.

10. Chang, L.C. Association schemes of partially balanced block designs with parameters v = 28, n = 12, no = 15 and — 4/ L.C. Chang // Sci. Record.- 1950, — Vol. 4, — P. 12−18.

11. Deza, A. The ridge graph of the metric polytope and some relatives/ A. Deza, M. Deza // in T. Bisztriczky, P. McMullen, R. Schneider and A. Ivic Weiss (eds.), «Polytopes: Abstract, Convex and Computational11 Dordrecht, Kluwer.- 1994, — P. 359−372.

12. Erickson, M. Deza Graphs: A Generalization of Strongly Regular Graphs/ M. Erickson, S. Fernando, W.H. Haemers, D. Hardy, J. Hemmeter //J. Combin. Designs.- 1999, — Vol. 7, — P. 395−405.

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

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

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

16. Hubaut Xavier L. Strongly regular graphs / L. Hubaut Xavier // Discret, Mathematics.- 1964. Vol. 13, — P. 357−381.

17. 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.

18. Shrickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhande // Ann. Math. Stat.- 1959, — Vol. 30, — P. 781−798.Работы автора по теме диссертации.

19. Ермакова, Г. М. Графы Деза, которые являются кликовыми расширениями сильно регулярных графов /' Г. М. Ермакова, В. В. Кабанов / Проблемы теорет. и прикл. математики: тр. 37-й регион, молодеж. конф. Екатеринбург: УрО РАН, 2006, — С. 27−29.

20. Ермакова, Г. М. Точные графы Деза без 3-коклик с большим ц / Г. М. Ермакова, В. В. Кабанов / Проблемы теорет. и прикл. математики: тр. 38-й молодеж. конф. Екатеринбург: УрО РАН, 2007. С. 31−34.

21. Ермакова, Г. М. Свойства графов без порожденных подграфов з/ Г. М. Ермакова, В. В. Кабанов, Е. Ш. Сабирзянова, Го Вэньбинь // Труды Института математики и механики Уральского отделения РАН, — 2008.Т. 14, — № 4. С. 43−52.

22. Ермакова, Г. М. Некоторые свойства точных графов Деза без 3-коклик с ?1 = b / Г. М. Ермакова / Проблемы теорет. и прикл. математики: тр. 40-й молодеж. конф. Екатеринбург: УрО РАН, 2009. С. 19−27.

23. Ермакова, Г. М. Характеризация одного класса графов без порожденных .ЙТ^з-подграфов/ Г. М. Ермакова, В.В. Кабанов/ Труды Института математики и механики Уральского отделения РАН.- 2009. Т. 15. № 2.C. 98−112.