Графы без 3-лап и сопутствующие частичные геометрии

Вакула, Игорь Александрович

Графы без 3-лап и сопутствующие частичные геометрии тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

Вакула, Игорь Александрович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Екатеринбург МЕСТО ЗАЩИТЫ

2005 ГОД ЗАЩИТЫ

01.01.04 КОД ВАК РФ

Диссертация по математике на тему «Графы без 3-лап и сопутствующие частичные геометрии»

Автореферат диссертации на тему "Графы без 3-лап и сопутствующие частичные геометрии"

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

ГРАФЫ БЕЗ 3-ЛАП И СОПУТСТВУЮЩИЕ ЧАСТИЧНЫЕ ГЕОМЕТРИИ

01.01.04 — геометрия и топология

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

ЕКАТЕРИНБУРГ, 2005

Работа выполнена в отделе алгебры и топологии ИММ УрО РАН.

Научный руководитель:

доктор физико-математических наук, с.н.с. Кабанов В. В.

Официальные оппоненты: доктор физико-математических

наук, профессор Рожков А. В.

кандидат физико-математических наук, профессор Суханов Е. В.

Ведущая организация:

Челябинский государственный педагогический университет

Защита диссертации состоится 28 июня 2005 года в 11 часов на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С.Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан 27 мая 2005 г.

И.о. учёного секретаря диссертационного совета,

доктор физ.-мат. наук

Белоногов В. А.

200&-4

14Ы

Общая характеристика работы

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

Первый источник лежит в области общей теории графов. Здесь и далее под словом граф мы понимаем конечный неориентированный граф без петель и кратных ребер. 3-лапой называется полный двудольный граф с долями из одной и трех вершин. О графе мы говорим, что он является графом без 3-лап, если он не содержит 3-лап в качестве порожденных подграфов. Класс графов без 3-лап содержит такой важный класс графов, как реберные графы. Реберным графом мы называем любой граф Г, который изоморфен графу £(Д), для подходящего графа А, где £(Д) — граф вершинами, которого являются ребра графа А, причем две вершины смежны тогда и только тогда, когда их пересечение одноэлементно.

Класс графов без 3-лап можно рассматривать как класс, являющийся наиболее интересным расширением класса реберных графов, при этом он гораздо шире, и вместе с тем графы этого класса наследуют многие свойства реберных графов. Треугольник Т (полный подграф на трех вершинах) графа Г называется нечетным, если в Г \ Т существует вершина смежная Г в точности с нечетным числом вершин. В [10] доказано, что следующие условия эквивалентны:

(1) Г — реберный граф;

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

Из ее формулировки видно, почему в качестве расширения класса реберных графов был выбран класс графов без 3-лап.

свойствам. Говорят, что граф обладает локально свойством Р, если подграф порожденный вершинами окрестности произвольной вершины этого графа обладет свойством Р. Окрестностью вершины V графа Г называется множество всех тех его вершин, обозначаемое [и], которые смежны с V. п-кликой (соотв. кокликой) графа Г называется любое его тг-подмножество любые две вершины которого смежны (соотв. несмежны) в Г. Таким образом, графы без 3-лап — это в точности графы, в которых окрестность всякой вершины не содержит 3-коклик. Можно сказать, что задача полного описания графов без 3-лап является задачей восстановления графа по информации о его локальной структуре. Эта задача в такой постановке в основном изучается для точечных графов конечных геометрий (см. [11]) и других комбинаторно-симметричных графов.

Сложность задачи восстановления графа по его локальным свойствам, в первую очередь связана с тем, что имея даже хорошее представление о строении окрестности каждой вершины графа в общем случае невозможно получить информацию о строении графа порожденного объединением окрестностей двух вершин графа, находящихся на расстоянии 1 и 2 в графе. Поэтому на этапе изучения необходимы дополнительные предположения о "взаимодействии"окрестностей вершин. Пусть а и Ь — вершины графа Г. Тогда подграф, порожденный пересечением [а] П [6] их окрестностей называется А-подграфом, если они смежны, и //-подграфом, если они находятся на расстоянии 2. Последний из них обозначается М(а, Ь). Именно строение //-подграфа М(а, Ь) позволяет связать свойства окрестностей вершины а и Ь. Скажем, что Г — граф с некликовыми //-подграфами, если любой его //-подграф содержит пару несмежных вершин. Вместе с тем, как нетрудно видеть, любой граф не содержащий 3-коклик является графом без 3-лап, поэтому для того, чтобы условие отсутствия 3-лап не было вырожденным необходимо потребовать, чтобы каждая связная компонента содержала 3-коклику. При этом, как нетрудно видеть, выполнение условия отсутствия 3-лап и неклико-вости //-подграфов для всего графа эквивалентно выполнению этих условий для всех его связных компонент. Итак, мы приходим к задаче изучения связных графов без 3-лап с некликовыми //-подграфами,

содержащих 3-коклику.

С другой стороны, класс графов без 3-лап с некликовыми ц-подграфами, содержащих 3-коклику, содержит некоторые важные семейства комбинаторно симметричных графов. Такими семействами, например, являются реберные графы полных и полных двудольных графов, соответственно, треугольные и решетчатые графы. Если Кп и К„чп — полный граф с п вершинами и полный двудольный граф с долями из гп и п вершин, то Т(п) = С(Кп) — треугольный граф, а С{Кт>п) — т х п-решетка. Треугольные графы и квадратные решетки (с т — п), в частности, обладают свойством сильно-регулярности. Граф Г называется сильно-регулярным, если он имеет диаметр 2, и существуют такие числа к, А, /л, что мощность окрестности любой вершины равна к, число вершин в любом А-подграфе равно А, а число вершин в любом //-подграфе равно /¿. Если V — число вершин графа Г, то говорят, что Г — сильно-регулярный граф с параметрами (V, к, А, ц).

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

Результаты настоящей работы обобщают результаты А. Врауэра, М. Нуматы и В.В. Кабанова.

Перейдем теперь к источнику связанному с конечными геометриями. Система инцидентности Б — (Р, В, I) с множеством точек Р, множеством блоков В и симметричным отношением инцидентности I с тем свойством, что 1С (Р х В) и (В х Р) называется геометрией ранга 2. Двойственная к Б геометрия Б0 = (Р°, 1°) получается, если положить Ри — В, Вв — Р и I = /. В случае, когда

В не содержит блоков инцидентных одним и тем же точкам из Р (неразличимых блоков), каждый элемент В можно отождествить с подходящим подмножеством из Р. Если такое отождествление имеется, то пишут S = (Р, В). Две точки называются коллинеарными, если обе они лежат в некотором блоке из В. Точечным графом называется граф с множеством вершин Р и отношением смежности, полученным удалением из отношения коллинеарности диагонали квадрата Р2. Точечный граф геометрии S обозначим TS. Иногда по точечному графу можно однозначно восстановить геометрию.

Для точки х положим х1 = {у € Р\х ~ у}, где ~ - отношение коллинеарности. Вычетом геометрии S в точке х называется геометрия Sx = (РХ,ВХ,1Х), где Рх = Xх \ {х}, Вх = {L\x £ L,L € В} и I = ТГ\((РХ х BT)ö(Bx х Рх)). Теперь мы можем сказать, что в случае, когда точечный граф определяет геометрию, задача восстановления этого графа по окресностям вершин эквивалентна восстановлению геометрии по ее вычетам. Задача восстановления графа по окрестностям вершин является сложной даже тохда, когда действие его группы автоморфизмов транзитивно на множестве вершин. Ситуация становится сложнее, если нам известно лишь то. что подграфы, порожденные окрестностями вершин попарно изоморфны (комбинаторный аналог вершинной транзитивности группы автоморфизмов графа). Однако в некоторых случаях приходится рассматривать графы, у которых подграф порожденный окрестностью произвольной вершины принадлежит некоторому классу графов Т. Тогда наличие единого структурного описания этого класса может быть полезным. Например, структурное описание класса графов без 3-лап с равно-мощными //, подграфами было полученно в работе [3]. Затем это описание было использовано в работах [2], [4], [5], [6] для характеризации графов Грассмана и Джонсона.

писать X, а вместо В — С. При этом элементы С называют прямыми. Обобщенным четырехугольником называется частичное линейное пространство, такое, что если точка х не лежит на прямой I, тогда х коллинеарна единственной точке прямой I. Обобщенный четырехугольник называется вырожденным, если некоторая точка коллинеарна всем остальным точкам. В вырожденном обобщенном четырехугольнике множество прямых образует пучок. Обобщенный четырехугольник определяется своим точечным графом, причем прямым соответствуют максимальные клики. Размер прямых обобщенного четырехугольника одинаков, за исключением случая, когда точечный граф изоморфен неквадратной решетке. Нетривиальные обобщенные четырехугольники с прямыми размера 3 описаны. Графы дополнительные к их точечным графам — это в точности 3 х 3-решетка, граф Т(6) и граф Шлефли (см. [9]). Все эти графы не содержат 3-лап и, как мы увидим, это не случайно. Геометрия, дополнительный граф к точечному графу которой изоморфен графу Шлефли, обозначается

Антифлагом называется пара (х, Ь), состоящая из точки и прямой, ее не содержащей. Положим а(х, Ь) — число точек инцидентных Ь и коллинеарных х. Пусть <р — натуральное число, частичное линейное пространство называется ^-однородным, если а(х, Ь) равно О или (р для любого антифлага, и сторого ср однородным, если а тождественно равно Фактически описание обобщенных четырехугольников с прямыми размера 3 — это описание строго 1-однородных частичных линейных пространств с прямыми размера 3. Вопрос описания 1-одпородных частичных линейных пространств с прямыми размера два и три открыт. Такие геометрии также однозначно определяются своими точечными графами.

Пусть 8 = (X, С) — частичное линейное пространство. Скажем, что Б строго 1-однородна на С С С, если для любого антифлага {х,Ь) с Ь € С имеем а(х,Ь) = 1. Аналогично определяется 1-однородность на С С С.

Определим подкласс I класса 1-однородных частичных линейных пространств, с прямыми размера не более трех. Пусть Э — геометрия из I, тогда:

((71) любая прямая в в имеет размер 2 (короткая) или 3(длинная);

((72) Б — 1-однородна на коротких прямых и строго 1-однородна на длинных прямых;

(С?3) для любого ребра в ГБ существует независимое от него ребро этого же графа.

Изучение класса I связано с изучением графов без 3-лап с некли-ковыми //-подграфами.

Цель работы. Работа посвящена описанию графов без 3-лап с некли-ковыми /¿-подграфами, содержащих 3-коклику. На его базе дается описание подкласса I класса конечных 1-однородных частичных геометрий.

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

Научная новизна. Все результаты диссертации являются новыми.

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

Апробация работы. Результаты работы докладывались на семинаре отдела алгебры и топологии института математики и механики УрО РАН, конференции по алгебре, логике и кибернетике, проходившей в Иркутске в августе 2004 года [16], на семинаре лаборатории теории графов Института математики СО РАН в октябре 2004 года, в Москве на конференции "Дискретные модели в теории управляющих систем "в декабре 2004 года [17], на региональной молодежной конференции в Екатеринбурге в январе 2005 года [13], в Екатеринбурге на семинаре "Алгебраические системы "кафедры алгебры и дискретной математики Уральского государственного Университета.

Публикации. Основные результаты диссертации опубликованы в работах [12]—[19].

Объем и структура диссертации. Диссертационная работа состоит из введения, пяти глав и списка литературы (21 наименование), занимает 90 страниц текста. Нумерация основных теорем во введении одинарная, теорем и лемм в главах двойная (номер главы и номер утверждения).

СОДЕРЖАНИЕ РАБОТЫ

Обозначим посредством К класс связных графов, удовлетворяющих следующим четырем условиям:

(г) Г не содержит 3-лап;

(И) всякий ц- подграф в Г содержит пару несмежных вершин;

(ш) Г содержит 3-коклику.

(гь) для любых вершин а, Ь графа Г условие а1- = ¿г1 влечет а = Ь.

Настоящая работа посвящена описанию графов класса К.

Пусть ж и у вершины графа Г, положим х = у тогда и только тогда, когда х1 = у-1. Легко видеть, что = является отношением эквивалентности. Фактор-граф Г графа Г по отношению = будем называть редукцией графа Г, а граф изоморфный редукции некоторого графа — редуцированным. Для графа Г, рассмотрим Г* граф, полученный из Г добавлением в него одной вершины а так, что в Г* выполняется равенство ах = Ь1- для некоторой вершины Ь из Г. Граф Д, полученный из Г посредством конечного числа таких операций, называется клиповым расширением графа Г. Нетрудно заметить, что если граф Г был редуцированным, то он изоморфен редукции А графа Д. Также ясно, что любой нередуцированный граф изоморфен некоторому кликовому расширению своей редукции.

Всякое кликовое расширение графа одновременно с ним удовлетворяет или не удовлетворяет условиям (г) - (иг). Следовательно, любой граф, удовлетворяющий условиям (г) - (ггг) является клико-вым расширением некоторого графа из класса К.

Выполнение условий (г), (гг) и (ги) для всего графа эквивалентно выполнению этих условий для каждой его связной компоненты. Поэтому вместо того, чтобы требовать наличия 3-коклики в каждой

компоненте связности, естественнее считать все изучаемые графы связными.

Пусть © — 3-коклика графа Г. Скажем, что граф Г натягивается на 3-коклику 0, если любая вершина из Г \ © смежна по крайней мере с двумя вершинами из ©.

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

(A) Г содержит 4-коклику;

(B) Г не содержит 4-коклик, но содержит 3-коклику, на которую он не натягивается;

В самом деле, графы из пунктов (А) и (В) не натягиваются на подходящие 3-коклики, в (В) это указывается явно, а в (Л) достаточно в качестве такой 3-коклики взять тройку вершин из произвольной 4-коклики. Подклассы из К, порождаемые этими условиями, обозначим, соответственно, К а, К в, К с- Графы из класса Кс оказывается естественным разбить на два подкласса, используя следующее условие:

(ЛГ) в Г существует 3-коклика © = {ох, а2, аз}, для которой найдутся вершины графа Г такие, что 1г\, — несмежные вершины из М(аг, аг+1) (здесь и далее сложение в индексах происходит по модулю числа его существенно различных минимальных значений), и такие, что подграф Н = {Уг \г = 1,2,Ъ\] = 1,2} состоит из пары независимых треугольников

Зададим теперь разбиение класса Кс на подклассы Ко и Ке, определив следующие условия:

(В) условие (N) не выполнено;

(Е) условие (./V) выполнено.

В главе 1 диссертации собраны вспомогательные результаты.

Во второй главе диссертации исследуется класс К^ и доказывается следующая теорема.

Теорема 1. Если связный граф Г принадлежит классу Кд, то Г

изоморфен реберному графу некоторого полного многодольного графа.

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

Будем говорить, что граф Г с множеством вершин V разбивается на 3 клики, если V = V\ U V2 U V3, где Vt попарно дизъюнктны и являются кликами графа Г.

В главе 3 описывается класс Кв- Из результатов полученных в этой главе вытекает следующая теорема:

Теорема 2. Если связный граф Г принадлежит классу К в, то Г изоморфен реберному графу некоторого полного многодольного графа, либо разбивается на 3 клики.

Пусть Ст — цикл длины т, где т — натуральное число, большее двух; натуральные числа ki, k2,..., ki таковы, что кх < к2 < ...< ki < J • Циркулянтом С(тп; fci, k2, . . . , h) называется граф с множеством вершин V(Cm) такой, что две его вершины смежны тогда только тогда, когда расстояние между ними в Ст принадлежит {ki, k2- ■ ■ ■ ■ ki}. Если в качестве вершин цикла Ст выбрать элементы кольца Zm, расположив их друг за другом, то и, г; из С(т; k2, • - ■, ki) смежны тогда и только тогда, когда и — v G {±/w. ±fc2> • • •, Рассмотрим кликовое расширение графа С(Зп; 1,2,..., п — 1), в котором каждая вершина in + j, где 1 < г < 3,1 < j < п, заменена на клику Q(i,j) мощности Qj, для некоторых натуральных чисел q\, q2,... ,qn. Соединим в этом кликовом расширении вершины каждого объединения U Cl(i,j) таким образом, чтобы получилась щ х 3-решетка,

1<г<3

и получим граф Q(n; qi, q2,..., qn).

В главе 4 диссертации описываются графы из класса Ко, разбиваемые на 3 клики, и графы из класса Кв, не являющиеся реберными и, как следует из теоремы 2, разбиваемые на 3 клики. Из результатов полученных в этой главе и теоремы 2 вытекает следующая теорема:

Теорема 3. Пусть связный граф Г принадлежит классу К в и ме является реберным, либо принадлежит классу Кц и разбивается на 8 клики. Тогда каждая вершина графа Г принадлежит некоторой 3-коклике этого графа тогда и только тогда, когда Г изоморфен графу 0(п; ql, ^, • • ■, дп), где каждое ql — натуральное, большее двух.

Наконец в главе 5 диссертации описываются класс К к и те графы из класса Кр, которые не разбиваюся на 3 клики. Из полученных результатов вытекает:

Теорема 4. Пусть связный граф Г принадлежит классу Ке или классу Кг>, причем в последнем случае не разбивается на 3 клики. Тогда, если каждая его вершина лежит в 3-коклике, то Г изоморфен некоторому подграфу графа Шлефли.

Таким образом из теорем 1-4 вытекает:

Теорема 5. Связный граф Г из класса К, каждая вершина которого лежит в 3-коклике, изоморфен реберному графу некоторого полного многодольного графа, либо изоморфен графу П(щ qъ q2, ■ ■ ■, qn), где каждое qi — натуральное, большее двух, либо изоморфен подграфу графа Шлефли.

Также в пятой главе диссертации доказывается, что геометрия 8 принадлежит классу I тогда и только тогда, когда граф дополнительный к ее точечному графу принадлежит классу К с- Это, в частности, означает, что в главах 4 и о описан класс геометрий I. В самом деле, как уже говорилось геометрии класса I однозначно определяются своими точечными графами.

Пусть Б = (X, С) — частичное линейное пространство. Пусть также X' С X и С' = {Ь П Х'\Ь е £ Л \Ь П Х'\ > 2}. Геометрия в' = (X', £') является частичным линейным пространством. Назовем Б' естественным подпространством пространства Б.

Геометрию из класса I, дополнительный граф которой изоморфен графу Г2(п; ^, • ■ •, Яп), где все qt равны 3, обозначим СО(п) и назовем циркулянтно-решетчатой геометрией.

Имеем:

Следствие. Пусть геометрия Б принадлежит классу I, а каждая ее тонка лежит на некоторой длинной прямой. Тогда Б изоморфна циркулянтно-решетчатой геометрии СС?(п) для некоторого натурального п, либо является естественным подпространством геометрии 0(^(2,4).

Список литературы

[1] Кабанов В.В. Характеризация треугольных и решетчатых графов // Сиб. мат. ж. 1998. Т. 39, С. 1054-1059.

[2] Кабанов В.В. О графах без корон с регулярными //-подграфами // Мат. заметки,- 2000.- Т.67, вып.6,- С.874-881.

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

[4] В.В. Кабанов, A.A. Махнев, Д.В. Падучих О локально решетчатых подграфах в графах Грассмана // Алгебра, логика и кибернетика: материалы междунар. конф.- Иркутск, 2004 - С. 149-151.

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

[6] Кабанов В.В., Махнев A.A., Падучих Д.В. Локальное строение графов без 3-корон с реберно регулярными //-подграфами // Междунар. конф. "Алгебра и ее прил.", Красноярск, 5-9 авг., 2002: Тез. докл.- Красноярск, 2002,- С.55-56.

[7] Харари Ф. Теория графов. М. Мир, 1973.

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

[9] Brouwer A.E., Cohen A.M., Neumaier A. Distance-Regular Graphs. Berlin e.a.: Springer, 1989.

[10] van Rooij A.C.N., Wilf H.S., The interchange graph of a finite graph // Acta Math. A.S.H., 1965, V. 16, P. 263-269.

[11] Makhnev A.A. Partial geometries and their extensions. Uspelhi Mat. Nauk 54:5, 1999, P. 25 - 76.

Работы автора по теме диссертации

[12] Вакула И. А. О графах без 3-лап с некликовыми //-подграфами. Международный семинар по теории групп, посвященный 70-летию А. И. Старостина и 80-летию Н. Ф. Сесекина. Екатеринбург, 17-21 декабря 2001 г. С. 42 - 45.

[13] Вакула И. А., Кабанов В.В. О графах без 3-лап с некликовыми /¿-подграфами. Международный семинар по теории групп, • посвященный 70-летию А. И. Старостина и 80-летию Н. Ф. Сесекина. Екатеринбург, 17-21 декабря 2001 г. С. 45 - 47. ^

[14] Вакула И. А. О графах без 3-лап с некликовыми //-подграфами. Алгебра и линейная оптимизация. Труды международного семинара, посвященного 90-летию со дня рождения С. Н. Черникова, 3-5 июня 2002 г. Екатеринбург, 2002. С. 66 - 80.

[15] Vakula I. A. On claw-free graphs with ион-clique //-subgraphs. Combinatorics 2002, Maratea (Potenza), june 2-8, 2002. P. 99-100.

[16] Вакула И.А., Кабанов В.В. Об одном классе графов без 3-лап. Алгебра, логика и кибернетика, Иркутск, 25-28 августа 2004 г. С. 117 - 122.

[17] Вакула И.А., Кабанов В.В. Об одном классе графов без 3-лап. Дискретные модели в теории управляющих систем, Москва, 7-12 декабря, 2004. С. 157-160.

[18] Вакула И.А. Графы без 3-лап с некликовыми //-подграфами натягиваемые на каждую свою 3-коклику. Проблемы теоретической и прикладной математики. Труды региональной молодежной конференции, 30 января - 4 февраля 2005. Екатеринбург, 2005.

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

Подписано в печать 23.05.05 Формат 60x84 1/16 Бумага писчая Плоская печать Тираж 70 экз. Заказ

Ризография научно-исследовательской части ГОУ ВПО УГТУ-УПИ 620002. г. Екатеринбург, ул. Мира 19.

РНБ Русский фонд

2006-4 14206

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Вакула, Игорь Александрович

Введение

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

К Глава 2. Графы, содержащие 4-коклику.

Глава 3. Графы, не натягиваемые на некоторую 3-коклику.

Глава 4. Графы, разбиваемые на три клики.

Глава 5. Графы, натягиваемые на любую 3-коклику

Введение диссертация по математике, на тему "Графы без 3-лап и сопутствующие частичные геометрии"

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

Первый источник лежит в области общей теории графов. Здесь и далее под словом граф мы понимаем конечный неориентированный граф без петель и кратных ребер. Если Г — граф, то посредством V(Г) и Е(Г) обозначим, соответственно, множество вершин и множество ребер графа Г. 3-лапой называется полный двудольный граф с долями из одной и трех вершин. Далее всюду, если не оговорено противное, подграф из Г будет означать порожденный подграф графа Г, то есть подграф, в котором вершины смежны тогда и только тогда, когда они смежны в Г. О графе мы говорим, что он является графом без 3-лап, если он не содержит подграфов изоморфных 3-лапе. Класс графов без 3-лап содержит такой важный класс графов, как реберные графы. Реберным графом мы называем любой граф Г, который изоморфен графу £(А), для подходящего графа А, где £(А) — граф вершинами, которого являются ребра графа А, причем две вершины смежны тогда и только тогда, когда их пересечение одноэлементно.

1) Г — реберный граф;

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

До последнего времени задача изучения графов без 3-лап при достаточно общих дополнительных ограничениях казалась сложной. Условие отсутствия 3-лап относится к, так называемым, локальным свойствам. Говорят, что граф обладает локально свойством Р, если подграф порожденный вершинами окрестности произвольной вершины этого графа об-ладет свойством Р. Если а — вершина графа Г, то через [а] будем обозначать окрестность вершины а, то есть множество вершин графа Г, смежных с а, а через а1 — объединение [a] U {а}, которое назовем замкнутой окрестностью вершины а. п—кликой (соотв. кокликой) графа Г называется любое его п—подмножество любые две вершины которого смежны (соотв. несмежны) в Г. Таким образом, графы без 3-лап — это в точности графы, в которых окрестность всякой вершины не содержит 3-коклик. Можно сказать, что задача полного описания графов без 3-лап является задачей восстановления графа по информации о его локальной структуре. Эта задача в такой постановке в основном изучается для точечных графов конечных геометрий (см. [13]) и других комбинаторно-симметричных графов.

Сложность задачи восстановления графа по его локальным свойствам, в первую очередь связана с тем, что имея даже хорошее представление

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

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

С другой стороны, класс графов без 3-лап с некликовыми р— подграфами, содержащих 3-коклику, содержит некоторые важные семейства комбинаторно симметричных графов. Такими семействами, например, являются реберные графы полных и полных двудольных графов, соответственно, треугольные и решетчатые графы. Если Кп и Кт>п — полный граф с п вершинами и полный двудольный граф с долями из тип вершин, то Т(п) = £(Кп) — треугольный граф, а £(Кт,п) — т х п—решетка. Треугольные графы и квадратные решетки (cm, — п), в частности, обладают свойством сильно-регулярности. Граф Г называется сильно-регулярным, если он имеет диаметр 2, и существуют такие числа к, А, р, что мощность окрестности любой вершины равна к, число вершин в любом Л—подграфе равно Л, а число вершин в любом //—подграфе равно р. Если v — число вершин графа Г, то говорят, что Г — сильнорегулярный граф с параметрами (и, к, Л, р).

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

Результаты настоящей работы обобщают результаты А. Брауэра, М. Нуматы и В.В. Кабанова.

Перейдем теперь к источнику связанному с конечными геометриями. Система инцидентности S = (Р, В, I) с множеством точек Р, множеством блоков В и симметричным отношением инцидентности I с тем свойством, что I С (Р х В) U (В х Р) называется геометрией ранга 2. Двойственная к S геометрия SD = (PD,^D,/D) получается, если положить Р° = В, BD = Р и I = I. В случае, когда В не содержит блоков инцидентных одним и тем же точкам из Р (неразличимых блоков), каждый элемент В можно отождествить с подходящим подмножеством из Р. Если такое отождествление имеется, то пишут S = (Р,В). Две точки называются коллинеарными, если обе они лежат в некотором блоке из В. Точечным графом называется граф с множеством вершин Р и отношением смежности, полученным удалением из отношения коллинеарности диагонали квадрата Р2. Точечный граф геометрии S обозначим ГS. Иногда по точечному графу можно однозначно восстановить геометрию.

Для точки х положим х1 = {у е Р\х ~ у}, где ~ — отношение коллинеарности. Вычетом геометрии S в точке х называется геометрия Sx = (PX,BXJX), где Рх = х±\ {rr}, Вх = {L\x е L,L е В) и 1 = 1 П ((Рх х Вх) U (Вх х Рх)). Теперь мы можем сказать, что в случае, когда точечный граф определяет геометрию, задача восстановления этого графа по окресностям вершин эквивалентна восстановлению геометрии по ее вычетам. Задача восстановления графа по окрестностям вершин является сложной даже тогда, когда действие его группы автоморфизмов транзитивно на множестве вершин. Ситуация становится сложнее, если нам известно лишь то, что подграфы, порожденные окрестностями вершин попарно изоморфны (комбинаторный аналог вершинной транзитивности группы автоморфизмов графа). Однако в некоторых случаях приходится рассматривать графы, у которых подграф порожденный окрестностью произвольной вершины принадлежит некоторому классу графов Т. Тогда наличие единого структурного описания этого класса может быть полезным. Например, структурное описание класса графов без 3-лап с равномощными р,—подграфами было полученно в работе [3]. Затем это описание было использовано в работах [2], [4], [5], [6] для харак-теризации графов Грассмана и Джонсона.

Наконец, еще один взгляд на изучаемую проблему дает теория конечных частичных геометрий. Частичное линейное пространство — это такая конечная геометрия ранга 2, в которой нет неразличимых блоков, а любые две точки принадлежат не более чем одному блоку, при этом каждый блок содержит по крайней мере две точки. В теории частичных линейных пространств вместо Р принято писать X, а вместо В — При этом элементы С, называют прямыми. Обобщенным четырехугольником называется частичное линейное пространство, такое, что если точка х не лежит на прямой I, тогда х коллинеарна единственной точке прямой I. Обобщенный четырехугольник называется вырожденным, если некоторая точка коллинеарна всем остальным точкам. В вырожденном обобщенном четырехугольнике множество прямых образует пучок. Обобщенный четырехугольник определяется своим точечным графом, причем прямым соответствуют максимальные клики. Размер прямых обобщенного четырехугольника одинаков, за исключением случая, когда точечный граф изоморфен неквадратной решетке. Нетривиальные обобщенные четырехугольники с прямыми размера 3 описаны. Графы дополнительные к их точечным графам — это в точности 3 х 3—решетка, граф Т(6) и граф Шлефли (см. [9]). Все эти графы не содержат 3-лап и, как мы увидим, это не случайно. Геометрия, дополнительный граф к точечному графу которой изоморфен графу Шлефли, обозначается GQ(2,4).

Антифлагом называется пара (х, L), состоящая из точки и прямой, ее не содержащей. Положим а(х, L) — число точек инцидентных L и колли-неарных х. Пусть ip — натуральное число, частичное линейное пространство называется «^—однородным, если а(х, L) равно 0 или (р для любого антифлага, и сторого «^—однородным, если а тождественно равно ip. Фактически описание обобщенных четырехугольников с прямыми размера 3 — это описание строго 1-однородных частичных линейных пространств с прямыми размера 3. Вопрос описания 1 -однородных частичных линейных пространств с прямыми размера два и три открыт. Такие геометрии также однозначно определяются своими точечными графами.

Пусть S = (X, С) — частичное линейное пространство. Скажем, что S строго 1—однородна на С С £, если для любого антифлага (х, L) с L е С имеем a(x,L) = 1. Аналогично определяется 1—однородность на С С С.

Определим подкласс I класса 1 -однородных частичных линейных пространств, с прямыми размера не более трех. Пусть S — геометрия из I, тогда:

G1) любая прямая в S имеет размер 2 (короткая) или 3(длинная);

G2) S — 1—однородна на коротких прямых и строго 1—однородна на длинных прямых;

G3) для любого ребра в TS существует независимое от него ребро этого же графа.

Изучение класса I связано с изучением графов без 3-лап с неклико-выми ^—подграфами.

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Вакула, Игорь Александрович, Екатеринбург

1. Кабанов В.В. Характеризация треугольных и решетчатых графов // Сиб. мат. ж. 1998. Т. 39, С. 1054-1059.

2. Кабанов В.В. О графах без корон с регулярными ^—подграфами // Мат. заметки.- 2000.- Т.67, вып.6.- С.874-881. Реф. // РЖ Мат.-2001.- 01.02-13В.240.

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

4. В.В. Кабанов, А.А. Махнев, Д.В. Падучих О локально решетчатых подграфах в графах Грассмана // Алгебра, логика и кибернетика: материалы междунар. конф.- Иркутск, 2004.- С. 149-151.

5. Кабанов В.В., Махнев А.А., Падучих Д.В. О графах без корон с регулярными /i—подграфами, II = On Crown-Free Graphs with Regular -Subgraphs, II // Мат. заметки.- 2003.- T.74, вып.З.- C.396-406. Реф. // РЖ Мат.- 2004.- 04.04-1 ЗВ.262.

6. Кабанов В.В., Махнев А.А., Падучих Д.В. Локальное строение графов без 3-корон с реберно регулярными /л—подграфами // Междунар. конф. "Алгебра и ее прил.", Красноярск, 5-9 авг., 2002: Тез. докл.- Красноярск, 2002.- С.55-56.

7. Харари Ф. Теория графов. М. Мир, 1973.

8. Brouwer А.Е., Numata М., A characterization of some graphs which do not contain 3-c!aws // Discrete Math. 1994. V. 124, P. 49-54.

9. Brouwer A.E., Cohen A.M., Neumaier A. Distance-Regular Graphs. Berlin e.a.: Springer, 1989.10. van Rooij A.C.N., Wilf H.S., The interchange graph of a finite graph // Acta Math. A.S.H., 1965, V. 16, P. 263-269.

10. K-T. Balinska, K.T. Zwierzynski, V.V. Kabanov, Algorithms for generating a class of subgraphs of Schlaffli graph // The Technical university of Poznan, 2002, CSC Report No. 488.

11. Beineke L.W. Derived graphs and digraphs I I Beitrage zur Graphentheorie, Leipzig, 1968, P. 17—33.

12. Makhnev A.A. Partial geometries and their extensions. Uspelhi Mat. Nauk 54:5, 1999, P. 25 76.Работы автора по теме диссертации

13. Вакула И. А. О графах без 3-лап с некликовыми /и-подграфами. Международный семинар по теории групп, посвященный 70-летию А. И. Старостина и 80-летию Н. Ф. Сесекина. Екатеринбург, 17-21 декабря 2001 г. С. 42-45.

14. Вакула И. А., Кабанов В.В. О графах без 3-лап с некликовыми /2-подграфами. Международный семинар по теории групп, посвященный 70-летию А. И. Старостина и 80-летию Н. Ф. Сесекина. Екатеринбург, 17-21 декабря 2001 г. С. 45 — 47.

15. Вакула И. А. О графах без 3-лап с некликовыми /л-подграфами. Алгебра и линейная оптимизация. Труды международного семинара, посвященного 90-летию со дня рождения С. Н. Черникова, 3-5 июня 2002 г. Екатеринбург, 2002. С. 66 -80.

16. Vakula I. A. On claw-free graphs with non-clique /^-subgraphs. Combinatorics 2002, Maratea (Potenza), june 2-8,2002. P. 99-100.

17. Вакула И.А., Кабанов В.В. Об одном классе графов без 3-лап. Алгебра, логика и кибернетика, Иркутск, 25-28 августа 2004 г. С. 117 — 122.

18. Вакула И.А., Кабанов В.В. Об одном классе графов без 3-лап. Дискретные модели в теории управляющих систем, Москва, 7-12 декабря, 2004. С. 157-160.

19. Вакула И.А. Графы без 3-лап с некликовыми /г-подграфами натягиваемые на каждую свою 3-коклику. Проблемы теоретической и прикладной математики. Труды региональной молодежной конференции, 30 января 4 февраля 2005. Екатеринбург, 2005.

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