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

• Вакула, Игорь Александрович
• кандидат физико-математических наук
• 2005

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

Введение

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Графы без 3-лап и сопутствующие частичные геометрии»

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

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

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

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

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

Из ее формулировки видно, почему в качестве расширения класса реберных графов был выбран класс графов без 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 наименования). Во введении обсуждается возникновение и актуальность вопроса, даются основные определения и приводятся основные результаты.

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

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.