Экстремальные свойства минимальных и минимальных по стягиванию k-связных графов

• Автор: Образцова, Светлана Анатольевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Санкт-Петербург
• Количество страниц: 82 с.

Содержание
Введение

Глава 1. Основные понятия

1.1. Определения

1.2. Используемые теоремы

Глава 2. Описание локальной структуры ^-связных графов

Глава 3. Особые вершины, входящие в А>разделяющее множество, отделяющее компоненту, состоящую из трех вершин.
Глава 4. Особые вершины, входящие в ^-разделяющее множество, отделяющее компоненту, состоящую из четырех вершин

Глава 5. Нижние оценки для

5.1. 5-связные графы

5.2. 6, 7, 8, 9 и 10-связные графы

Глава 6. Верхние оценки для
6.1. 5-связные графы
6.2. к-связные графы
6.3. Случай нечетного к
6.4. Случай четного к
Список литературы
Введение
Минимальные и минимальные по стягиванию к-связные графы.
Эта диссертация посвящена изучению понятия вершинной связности, которое является одним из естественных обобщений понятия связности и, вследствие этого, имеет большое теоретическое и практическое значение. Многие практические задачи, в частности, имеющие отношение к надежности различных систем связи и транспортных сетей, могут быть сформулированы в терминах вершинной связности подходящих графов. Некоторые примеры использования вершинной связности можно найти в книге [6, глава 20]. В этой работе будут рассматриваться к-связные графы, то есть графы, содержащие как минимум к + 1 вершину, и сохраняющие связность при удалении произвольных к — 1 вершин. Началом исследований свойств Аьсвязности графа традиционно считается опубликованная в 1927 году К. Менгером работа [22], результаты которой стали наиболее существенными в этой области теории графов на несколько следующих десятилетий.
В 60-х годах XX века начались исследования сохранения /с-связности графов при различных операциях, таких как удаление вершин, удаление ребер или стягивание различных подмножеств множества вершин графа в одну вершину. В отличие от случая связности, когда в любом связном графе существует вершина, в результате удаления которой получается связный граф, существуют Аьсвязные графы, которые при удалении любой вершины теряют Аьсвязность. Например, простой цикл является двусвязным графом, но при удалении любой его вершины образуется граф, не являющийся двусвязным. Образуется естественный класс графов, называемых критическими к-связными графами, то есть графы, теряющие Аьсвязность при удалении любой вершины. Аналогично граф называется минимальным /с-связным графом, если при удалении любого ребра понижается его связность, и мини-

мальным по стягиванию /с-связным графом, если при стягивании любого ребра понижается его связность.
Интерес к минимальным и минимальным по стягиванию графам возник после работы У. Татта {35], в которой было дано полное описание структуры трехсвязного графа в терминах удаления и стягивания ребер. У. Татт доказал, что из любого трехсвязного графа при помощи удаления и стягивания ребер можно получить колесо — граф, состоящий из простого цикла и вершины, смежной со всеми вершинами этого цикла. Существенно, что все графы, получающиеся на промежуточных шагах этого процесса также трехсвязные. Теория Татта описана также в работах [34] и [36]. Аналогичные теории для к — 2 и к = 4 описаны в работах [12] и [30] соответственно. Вопрос о возможности построения подобной теории для произвольного к обсуждается в работе [31]. Вопрос о том, какова структура минимального и минимального по стягиванию /с-связного графа для к больших 3 был рассмотрен в статье Р. Халина [9]. В этой же статье был задан вопрос о том, какова константа щ. такая что количество вершин степени к в любом минимальном и минимальном по стягиванию к-связном графе Є равно по крайней мере с;.|&'|. Кроме того, в этой статье получены первые нижние оценки для С)- при к =■ 4, 5, 6.
На настоящий момент ситуация с верхними оценками чрезвычайно проста: никаких верхних оценок для с*, при к > 5 не существует (ни общих, ни для частных случаев к). Существующие верхние оценки для минимальных или минимальных по стягиванию графов построены на основании графов обладающих строго одним из указанных свойств (см., например, [1], [4], [17] и [20]). Кроме того, для минимальных по стягиванию графов эти оценки существуют только для к = 5, 6. До настоящего момента не было опубликовано примеров минимальных и минимальных по стягиванию /с-связных графов, содержащих вершину степени выше к.
С другой стороны, в 1981 году в работе Томассена [33] была построена серия примеров минимальных по стягиванию Аьсвязных ^-регулярных гра-

Глава
Особые вершины, входящие в /с-разделяющее множество, отделяющее компоненту, состоящую из четырех вершин.
В этой главе во всех леммах будет предполагаться, что х — особая вершина. Компонента # — наименьшая по количеству вершин компонента, отделяемая ^-разделяющим множеством, содержащим х и одну из смежных с ней вершин; ^-разделяющее множество, отделяющее компоненту Н, будем обозначать через Т, а вершину множества Т, смежную с х, — через у. Кроме того, через Тху будет обозначаться множество Т {х,у}.
Лемма 22. Пусть Н состоит из 4 вершин и ровно две из них имеют степень выше к. Обозначим эти вершины через а и а2 и предположим, что а и 02 смежны. Две другие вершины Н обозначим а3 и 04. Тогда одна из вершин аз и 04 (не умаляя общности можно считать, что аз) отвечает, следующим свойствам
(1) аз смежна по крайней мере с одной из вершин а,а2, смежной с х;
(2) а3 смежна с не более чем тремя вершинами степени выше к и не более одной из них входит в Т.
Доказательство. Заметим, что дн(сц) < 3 и дл{а2) < 3. Следовательно, {N0(01) П Т > к — 2 и Ма(а2) ПТ| > к — 2. Таким образом, каждая из вершин о 1 и 02 может быть несмежна не более чем с двумя вершинами из Т. Рассмотрим четыре случая: обе вершины 03 и а2 несмежны не более чем с одной вершиной из Т (случай (1)), одна из вершин 01 и 02 несмежна ровно с одной вершиной из Т, а другая — несмежна с двумя вершинами из Т (случай (2)), обе вершины а3 и а2 несмежны ровно с двумя вершинами из Т (случай