Исследование максимального рода графов

• Автор: Глухов, Александр Дмитриевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Киев
• Количество страниц: 92 c. : ил

В в е д е н и е

ГЛАВА I. ОБЩИЕ СВОЙСТВА МАКСИМАЛЬНОГО РОДА ГРАФОВ

§ 1.1. А- разложения, хордовость и максимальный род графов

§ 1.2.0-хордовые графы

§ 1.3.Хордово критические графы

§ 1.4.Существенность ребер графа относительно

максимального рода

ГЛАВА 2. НАХОЖДЕНИЕ МАКСИМАЛЬНОГО РОДА ГРАФОВ

§ 2.1.Циклическая связность и максимальный род

графов

§ 2.2.Максимальный род плоских графов

§ 2.3.Полиномиальный алгоритм нахождения максимального рода связного графа
§ 2.4.Применения полученных результатов
Л и т е р а т у р а
П р и л о ж е н и е

Одна из наиболее важных и интересных проблем современной теории графов заключается в определении множества родов всех компактных ориентируемых 2-многообразий, в которые граф вкладывается 2-клеточно. Согласно известной теореме Р.А.Дьюка [27] о промежуточных вложениях, связный граф б- вкладывается в ориентируемое 2-многообразие б'у рода V 2-клеточно тогда и только тогда, когда
Iх(&)4 V* гм(е),
где (С-) - абсолютный, а ^м(б)- максимальный роды графа б.
В то время как исследования абсолютного рода (или просто рода) графов имеют почти столетнюю историю (первой работой в этой области можно считать статью П.Хивуда (30]), первые публикации, посвященные максимальному роду графов, относятся к
1970 году. Это, в первую очередь работа Н.П.Хоменко и Э.Б.Яворского [21], в которой с помощью метода У- преобразований впервые был найден критерий 1-компонентной 2-клеточной вложимости графа б в ориентируемое 2-многообразие , представляющий собой следующее утверждение.
Теорема 9 [21]. Граф 0- вкладывается в ориентируемое 2-многообразие б'у 1-компонентно 2-клеточно тогда и только тогда, когда в нем существуют такие V независимых пар смежных ребер, после удаления которых остается фактордерево графа б.
С помощью этого критерия авторам удалось установить роды ориентируемых 2-многообразий, в которые I- или 2-компонентно 2-клеточно вкладываются графы Кп, (]п, Кп,п . Тем самым впервые был найден максимальный род этих графов.
Понятие максимального рода графов было, однако, введено в
1971 году Е.А.Нордхаузом, Б.М.Стюартом и А.Т.Уайтом в работе

(42], в которой также (другим методом) был найден максимальный род графа Кп . Эти же авторы вместе с Р.Д.Рингайзеном в работе [41] нашли условия, при которых максимальный род графа равен .нулю. Р.Д.Рингайзен в работе[45]нашел максимальный род некоторых плоских графов, а в работе[46]- максимальный род графа Кт,п. В работе/47]Р.Д.Рингайзен ввел в рассмотрение класс сверху вложимых графов , т.е. таких графов О , для которых
Гн(&) = I , изучил ряд свойств этих графов и высказал несколько гипотез.
В 1973 году вышел в свет ряд работ, посвященных исследованию максимального рода графов с помощью метода у> - преобразований. Особое место среди этих работ заняла статья Н.П.Хоменко,
Н.А.Островерхого и В.А.Кузьменко [19] , в которой была доказана следующая фундаментальная в теории максимального рода графов теорема.
ТеоремаА [19] . Максимальный род произвольного графа & равен максимальному числу таких независимых пар смежных ребер в 6- , что граф, полученный из & в результате удаления всех ребер этих пар, будет связным факторграфом графа Ог
Благодаря этому результату был найден максимальный род полных К- дольных, диаметрально-критических и других классов графов. В работе Н.А.Островерхого и В.А.Кузьменко [II] с помощью теоремы А [19] был найден максимальный род декартового, сильного декартового и лексикографического произведений двух графов, а в работе Н.А.Островерхого [ю] - найден максимальный род некоторых произвольных графов.
Интересно отметить, что практически все результаты, полученные к 1973 году в области максимального рода графов, можно более или менее просто вывести из теоремы А {[19] . Это относится к результатам работ [10,11,19,41,42,45,46], также к результа-

будет подграфом графа £ , к = ^н{£')> В силу леммы 2.2, будет справедливо равенство:
2 р((е/У°(Р7'(£'7) = 2к-г,
1-1 •>
а поэтощ и равенство:
1-1
Откуда, учитывая, что />*(V) ~ к- ссг-с/ке) *с / -£ ? получаем неравенство
2 Р ((С/’)0, {Сс")0) ± М~6.
С-П
С другой стороны, так как граф С- циклически нечетно 4-реберно связен и 2. , то будет справедливо следующее неравенство:
ев^Гфф)ъ4А,
которое противоречит предыдущему. Таким образом, доказано, что граф & сверху вложимый.
Следствие [44]. Любой циклически 4-реберно связный граф сверху вложимый.
Теорема 2.2. Если - циклически 3-реберно связный не сверху вложимый граф, то
г"(е) г г
Доказательство. Пусть & - циклически нечетно 3-реберно связный не сверху вложимый граф и пусть & = его экстремальное Л- разложение, которому не подчинено никакое другое экстремальное Я- разложение графа . Тогда, в силу следствия I теоремы 1.1, имеют место соотношения: