Экстремальные свойства минимальных и минимальных по стягиванию k-связных графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Санкт-Петербургский государственный университет

4849314

Образцова Светлана Анатольевна

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

от-

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

специальность 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2011 г.

9 ИЮН 2011

4849314

Работа выполнена в лаборатории математической логики Учреждения Российской академии наук Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН

Научный руководитель: кандидат физико-математических наук,

Пастор Алексей Владимирович

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

профессор Дольников Владимир Леонидович (Ярославский государственный университет имени П. Г. Демидова )

кандидат физико-математических наук, Берлов Сергей Львович (Государственное Общеобразовательное учреждение Фнзико-Математический Лицей №239 Центрального Района Санкт-Петербурга)

Ведущая организация: Учреждение Российской академии наук

Институт математики им. С. Л. Соболева Сибирского отделения РАН

Защита состоится » .... UM2.hU......... ... 2011 г. в часов на

заседании совета Д 212.232.29 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 191023, Санкт-Петербург, наб. р. Фонтанки, д. 27, комн. 311 (помещение ПОМИ РАН).

Адрес диссертационного совета: 198504, Санкт-Петербург, Ст. Петергоф, Университетский пр. д. 28.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан >>

...........20и г.

Ученый секретарь диссертационного совета Д 212.232.29

доктор физ.-мат. наук, профессор ./у В. М. Нежинский

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

Актуальность темы. Диссертация посвящена изучению понятия вершш ной связности, которое является одним из естественных обобщений понятия свя. ности и, вследствие этого, имеет большое теоретическое и практическое знач иие. В работе рассматриваются к-связпые графы, то есть графы, содержащие ка минимум к + 1 вершину, и сохраняющие связность при удалении произвольны к— 1 вершин. Изучаются ¿-связные графы, обладающие следующими двумя сво! ствами: минимальностью и минимальностью по стягиванию, то есть ¿-связны графы, которые теряют ¿-связность как при удалении любого ребра, так и пр стягивании любого ребра.

Интерес к минимальным и минимальным по стягиванию графам возник п еле работы У. Татта, в которой было дано полное описание структуры трехсвя: ного графа в терминах удаления и стягивания ребер. У. Татт доказал, что любого трехсвязного графа при помощи удаления и стягивания ребер можно п лучить колесо — граф, состоящий из простого цикла и вершины, смежной с всеми вершинами этого цикла. Существенно, что все графы, получающиеся н промежуточных шагах этого процесса, также трехсвязные. Вопрос о том, каков структура минимального и минимального по стягиванию ¿-связного для к боль ших 3, был рассмотрен в статье Р. Халина в 1969 году. В этой статье был зада вопрос о том, какова константа сь, такая что количество вершин степени к в лю бом минимальном и минимальном по стягиванию ¿-связном графе С равно п крайней мере в этой же статье и были получены первые нижние оценк

для Ск при к = 4,5,6.

На настоящий момент ситуация с верхними оценками для Ск чрезвычайн проста: никаких верхних оценок для Ск при А; > 5 не существует (ни общих, н для частных случаев к). Существующие верхние оценки для минимальных ил минимальных по стягиванию графов построены на основании графов обладающи строго одним из указанных свойств. Кроме того, для минимальных по стягиванш графов эти оценки существуют только для к — 5,6.

Результаты, касающиеся нижних оценок для значительно более разнооб разны. Начиная с 70-х годов исследовались в основном ¿-связные графы обла дающие только одним из двух свойств — минимальностью или минимальность! по стягиванию. Наибольшее продвижение в первом из этих направлений был

получено В. Мадсром. Он доказал, что в минимальном к-связном графе любой цикл содержит по крайней мере одну вершину степени к. Следствием этого утверждения является следующая нижняя оценка на долю вершин степени к от всего множества вершин — ^¡рр

Общих результатов во втором направлении получено не было, но существуют продвижения в изучении 4, 5, 6 и 7-связных графов. Случай 4-связных графов полностью описан в работах М. Фонте и Н. Мартинова, для 4-связных графов также получено, что из минимальности по стягиванию следует минимальность и доказано, что С4 = 1, то есть все вершины такого графа имеют степень 4. Для графов более высокой связности существуют примеры минимальных по стягиванию, но не минимальных графов, и, таким образом, рассмотрение графов, обладающих обоими свойствами, становится содержательным. Структура минимальных по стягиванию 5-связных графов подробно изучена в серии статей К. Андо, А. Ка-неко и К. Каварабаяши. В этой серии доказано, что в минимальном но стягиванию 5-связном графе любая вершина смежна по крайней мере с двумя вершинами степени 5. Из этого утверждения следует нижняя оценка на долю количества вершин степени 5, полученная К.Андо, а именно

Параллельно с работами К. Андо и др. минимальные по стягиванию 5-связные графы рассматривались в серии статей Ж. Су, Кс. Юана и Ч. Куина, в которой ыли получены аналогичные результаты и доказана более сильная оценка количества вершин степени 5. К сожалению, первые работы этой серии публиковались олько по-китайски. Лучшая оценка в серии составляет Кроме того, эти авторы указывают на невозможность улучшения оценки, полученной К. Андо и ф., с помощью прежних методов (т.е. изучения числа вершин степени 5 только в крестности вершин графа, без рассмотрения вершин, находящихся на расстоянии ольше 1), ссылаясь на приведенный в одной из статей серии пример минималь-юго по стягиванию 5-связного графа, окресности некоторых вершин степени 5 оторого содержат ровно две вершины степени 5. Впрочем, отметим, что при-еры графов, в которых значительное число вершин имеет ровно двух соседей тепени 5, приводились также в работах К. Андо и др.

Относительно минимальных по стягиванию 6-связных графов полученные родвижения значительно скромнее. К. Андо и др. доказали, что для любого инимального по стягиванию 6-связлого графа б выполнено |1'(;(С)| > ||С?|.

История изучения 7-связных графов несколько длинее, поскольку даже небо/ шие продвижения для этих графов требовали существенных усилий. Существ вание хотя бы одной вершины степени 7 в минимальном по стягиванию 7-связнох графе было получено как следствие результата Е. Эгава. Позднее, М. Криселл д казал существование двух вершин степени 7 и предположил существование таки вершин на расстоянии не более двух. Ж. Су и Кс. Юан это предположение д казал и. В дальнейшем Ж. Су, Кс. Юан и Л. Мин значительно улучшили оценку полученную К. Андо, и доказали, что для любого минимального по стягивани 7-связного графа выполнено \У~{С)\ >

Для минимальных по стягиванию /с-связных графов при к > 8 пока не доказано даже утверждение о существовании хотя бы одной вершины, имеюще степень к.

Цель работы.

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

2. С помощью полученных структурных лемм доказать нижние оценки дляс*. при к = 5,6,7,8,9,10.

3. Получить верхние оценки для с^ для произвольного к > 5.

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

Основные результаты работы.

1. Доказаны нижние оценки для с* при к = 5,6,7,8,9,10, а именно | для к = 5 и ± для к = 6,7,8,9,10.

2. Построены серии минимальных и минимальных по стягиванию ¿-связных графов и на их основе доказаны верхние оценки для с^ при произвольном к > 5. При этом получены следующие оценки:

• для к = 5,6,7,8,9,10 (с учетом п.1) доказано, что | < cs < Ц, | < со < Ц-,

1 г ^ / М 1 <Г /. ^ « 1 ^ 9 1 <Г ^ ^ 401.

2 < СГ < 45, J S С8 < 2 < tfl < 2 < С10 < дщ,

• для нечетного к > 5 доказано, что с* < ffiipffjg, где к = 2£ + 3;

• для четного к > 5 доказано, что с.к < ^T'-^mcf2' ^ =

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

Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты работы могут быть использованы для дальнейшего изучения свойств ^'-связных графов. В частности, структурные леммы, являющиеся промежуточными результатами данной работы, могут быть использованы в дальнейшем для изучения минимальных и минимальных по стягиванию fc-связных графов, где к > 10.

Апробация работы. Результаты диссертации докладывались на семинаре по дискретной математике ПОМИ РАН и на семинаре в Max Planck Institute for mathematics, Bonn, Germany.

Публикации. Основные результаты диссертации опубликованы в работах [1-4]. Работы [1,2] опубликованы в издании, входящем в список рекомендованных Высшей аттестационной комиссией на момент публикации. В работах [2,3) диссертанту принадлежит основная идея доказательства и часть технических выкладок. Соавтору принадлежит постановка задачи, формулировки ряда теорем и оставшаяся часть технических выкладок.

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

Содержание диссертации

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

В первой главе даются основные определения и приводятся уже известные результаты, используемые в дальнейшем. Там же вводится понятие особой вершины, то есть вершины степени к, несмежной с другими вершинами степени к.

Изучение особых вершин играет ключевую роль при доказательстве нижних оценок. Для минимального /с-связнош графа, не содержащего особых вершин, при помощи теоремы В. Мадера легко доказывается, что не менее половины вершин графа имеют степень к. Поэтому для доказательства нижних оценок нам нужно оценить сверху количество особых вершин минимального и минимального по стягиванию ^-связного графа.

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

Лемма 11. Пусть С? — минимальный по стягиванию /с-связный граф и |С| > 2к. Рассмотрим произвольную вершину графа и обозначим ее а. Тогда существует ^-разделяющее множество Т, содержащее а и по крайней мере одну из смежных с ней вершин, отделяющее компоненту, содержащую не более ^ вершин.

Для изучения окрестности особой вершины рассматривается минимальная компонента, отделяемая ¿-разделяющим множеством, содержащим рассматриваемую особую вершину и вершину, с ней смежную. Благодаря лемме 11 рассмотрение таких компонент сводится к конечному разбору случаев.

В этой же главе доказывается следующая теорема.

Теорема 5. В минимальных и минимальных но стягиванию 6-связных графах особых вершин не существует.

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

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

В четвертой главе изучаются вершины, находящиеся на расстоянии 1 и 2

от особой вершины, содержащейся, вместе с вершиной с ней смежной, только в ¿-разделяющих множествах, отделяющих компоненту из 4 вершин.

В пятой главе доказываются нижние оценки на с^ при ¿ = 5,6, 7,8, 9,10. Для доказательства оценок в случаях 7,8,9,10 доказываются следующие существенные структурные леммы.

Лемма 29. Пусть б — минимальный и минимальный относительно стягивания ¿-связный граф, где к € {7,8} и |&'| > 2к. Тогда количество особых вершин графа С не превосходит количества вершин степени к, смежных как минимум с двумя вершинами степени к.

Лемма 30. Пусть б — минимальный и минимальный относительно стягивания ¿-связный грае}), где к € {9,10} и |(7| > 2¿. Обозначим через 5ц множество всех особых вершин графа С и через — множество вершин степени к, смежных хотя бы с шестью вершинами степени к. Тогда 4|5г| > |5о|-

Теорема 8. Выполнены следующие неравенства: С5 > | и Ск > 5, где к = 6,7,8,9,10.

В шестой главе строятся три серии минимальных и минимальных по стягиванию ¿-связных графов, отдельно для 5, четного и нечетного к. С помощью построеных графов доказываются верхние оценки для с*. Теорема 10. Выполнено неравенство С5 < Ц.

Теорема 12. Предположим, что ¿ > 6 — нечетное число и к = 21 + 3. Тогда выполнено неравенство с* < ^г^Щ^-

Теорема 14. Предположим, что к > 6 — четное число и ¿ = 2£. Тогда выполнено неравенство с* < ш3-42е+2в •

Таким образом, для к = 5,6,7,8,9,10 в пятой и шестой главах получены следующие оценки: | < с5 < Ц, | < сс < \ < с7 < \ < с8 < |§, \ < Сд < д,

2 < СЮ < ею-

Работы автора по теме диссертации Статьи в журналах, рекомендованных ВАК:

[1] С.А.Образцова, О локальной структуре 5 и 6-связпых графов, // Записки научных семинаров ПОМИ, 381 (2010), 88-96.

[2] С.А.Образцова, А.В.Пастор, О локальной структуре 1 и 8-связных графов, Ц Записки научных семинаров ПОМИ, 381 (2010), 97-111.

Другие публикации:

[3| С.А.Образцова, А.В.Пастор, О вершинах степени к минимальных и минимальных относительно стягивания к-связных графов: верхние оценки, // ПОМИ препринт, 5/2011.

[4] С.А.Образцова, О локальной структуре 9 и 10-связных графов, // ПОМИ препринт, 6/2011

Подписано в печать «10» мая 2011 г. Формат 60x84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1,3. Тираж 100 экз. Заказ № 351

Типография «Восстания -1» 191036, Санкт-Петербург, Восстания, I.

Содержание.

Введение.

Глава 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] соответственно. Вопрос о возможности построения подобной теории для произвольного к обсуждаеггс51 в работе [31]. Вопрос о том, какова структура минимального и минимального по стягиванию /с-связного графа для к больших 3 был рассмотрен в статье Р. Халина [9|. В этой же статье был задан вопрос о том, какова константа такая что количество вершин степени к в любом минимальном и минимальном по стягиванию /с-связном графе С? равно по крайней мере Кроме того, в этой статье получены первые нижние оценки для С& при к = 4, 5, 6.

На настоящий момент ситуация с верхними оценками чрезвычайно проста: никаких верхних оценок для с& при к > 5 не существует (ни общих, ни для частных случаев к). Существующие верхние оценки для минимальных или минимальных по стягиванию графов построены на основании графов обладающих строго одним из указанных свойств (см., например, [1], [4], [17] и [20]). Кроме того, для минимальных по стягиванию графов эти оценки существуют только для к = 5,6. До настоящего момента не было опубликовано примеров минимальных и минимальных по стягиванию /с-связных графов, содержащих вершину степени выше к.

С другой стороны, в 1981 году в работе Томассена [33] была построена серия примеров минимальных по стягиванию /с-связных к-регулярных графов.

В диссертации строятся три серии минимальных и минимальных по стягиванию /с-связных графов, содержащих значительную долю вершин степени выше к и доказываются верхние оценки для Ск для произвольного к > 5, причем при к —> оо полученные верхние оценки для сходятся к

Результаты, касающиеся нижних оценок для с^, значительно более разнообразны. Начиная с 70-х XX века годов исследовались в основном к-связные графы обладающие только одним из двух свойств — минимальностью или минимальностью по стягиванию. Наибольшее продвижение в первом из этих направлений было получено В. Мадером в статье [18]. В. Мадер доказал, что в минимальном /с-связном графе любой цикл содержит по крайней мере одну вершину степени к. Следствием этого утверждения является следующая нижняя оценка на долю вершин степени к от всего множества вершин — ^гг- В дальнейшем, для графов, являющихся одновременно минимальными и минимальными по стягиванию не было получено оценок, улучшающих оценки В. Мадера.

Общих результатов во втором направлении получено не было, но существуют продвижения в изучении 4, 5, 6 и 7-связных графов. Случай 4-связных графов полностью описан в работах М. Фонте [8] и Н. Мартинова [21], для 4-связных графов также получено, что из минимальности по стягиванию следует минимальность и доказано, что с\ = 1, то есть все вершины такого графа имеют степень 4. Для графов более высокой связности существуют примеры минимальных по стягиванию, но не минимальных графов, и, таким образом, рассмотрение графов, обладающих обоими свойствами, становится содержательным. Структура минимальных по стягиванию 5-связных графов подробно изучена в серии статей К. Андо, А. Канеко и К. Каварабаяши [2],[5] и [1], завершающейся статьей [1]. В этой статье доказано, что в минимальном по стягиванию 5-связном графе любая вершина смежна по крайней мере с двумя вершинами степени 5. Из этого утверждения следует нижняя оценка на долю количества вершин степени 5, полученная К.Андо в [1], а именно

Параллельно с работами К. Андо и др. минимальные по стягиванию 5-связные графы рассматривались в серии статей Ж. Су, Кс. Юана и Ч. Куина [37], [32], [29], [28] и [16], в которой были получены аналогичные результаты и доказана более сильная оценка количества вершин степени 5. К сожалению, первые работы этой серии публиковались только по-китайски. Лучшая оценка в серии получена в работе [16]. Полученная в этой работе нижняя оценка на долю количества вершин степени 5 среди всех вершин минимального по стягиванию 5-связного графа составляет

Кроме того, эти авторы в [28] указывают на невозможность улучшения оценки, полученной К. Андо и др., с помощью прежних методов (т.е. изучения числа вершин степени 5 только в окрестности вершин графа, без рассмотрения вершин, находящихся на расстоянии больше 1), ссылаясь на приведенный в [29] пример минимального по стягиванию 5-связного графа, окресности некоторых вершин степени 5 которого содержат ровно две вершины степени 5. Впрочем, отметим, что примеры графов, в которых значительное число вершин имеет ровно двух соседей степени 5, приводились также в работах К. Андо и др., например, в [5]. В этой работе К. Андо, А. Канеко и К. Каварабаяши была получена верхняя оценка на долю вершин количества вершин степени 5 среди всех вершин минимального по стягиванию 5-связпого графа. Пример, построенный для доказательства верхней оценки, к сожалению, не может использоваться для получения верхней оценки для минимальных и минимальных но стягиванию 5-связных графов, поскольку содержит значительное и труднооцениваемое количество несущественных ребер. (Ребро называется несущественным, если при его удалении связность графа не уменьшается.)

Относительно минимальных по стягиванию 6-связных графов полученные продвижения значительно скромнее. В [4] К. Андо и др. доказали, что для любого минимального по стягиванию 6-связного графа (7 выполнено

- 7> В этой же работе приведен пример минимального по стягиванию 6-связного графа, в котором = \\G\- Этот пример, также как и пример для 5-связного графа, содержит значительное число несущественных ребер и не дает возможности получить верхнюю оценку для минимального и минимального по стягиванию 6-связного графа.

История изучения 7-связных графов несколько длинее, поскольку даже небольшие продвижения для этих графов требовали существенных усилий. Существование хотя бы одной вершины степени 7 в минимальном по стягиванию 7-связном графе было получено как следствие результата Е. Эгава [7]. Позднее, М. Криселл в [15] доказал существование двух вершин степени 7 и предположил существование таких вершин на расстоянии не более двух. Ж. Су и Кс. Юан в [38] это предположение доказали. В дальнейшем К. Андо, А. Канеко и К. Каварабаяши получили, но не опубликовали, нижнюю оценку (см. [3]) на долю вершин степени 7 в минимальном по стягиванию 7-связном графе, которую Ж. Су, Кс. Юан и Л. Мин в [17] значительно улучшили, доказав, что для любого минимального по стягиванию 7-связного графа выполнено > В [17] также построена серия примеров графов С, для которых У7(С) состоит из изолированных вершин и высказано предположение, что других примеров минимальных по стягиванию 7-связных графов, не содержащих смежных вершин степени 7, не существует. Особенностью этого примера является то, что при удалении всех несущественных ребер степени всех вершин графа становятся равными 7.

Для минимальных по стягиванию ^-связных графов при к > 8 пока не доказано даже утверждение о существовании хотя бы одной вершины, имеющей степень к.

Таким образом, наилучшими оценками для с^ до настоящего момента были оценки, полученные для минимальных графов В.Мадером. В диссертации исследуется структура минимальных и минимальных по стягиванию к-связных графов и доказываются нижние оценки для с/с при к — 5,6, 7, 8, 9,10, а именно | для к = 5 и | для /с = 6, 7, 8, 9,10.

Результаты и структура диссертации

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

В первой главе даются основные определения и приводятся уже известные результаты, используемые в дальнейшем. Там же вводится понятие особой вершины, то есть вершины степени к, несмежной с другими вершинами степени к. Изучение особых вершин играет ключевую роль при доказательстве нижних оценок. Для минимального и минимального по стягиванию /¿-связного графа, не содержащего особых вершин, при помощи теоремы В. Мадера легко доказывается, что не менее половины вершин графа имеют степень к. Поэтому для доказательства нижних оценок нам нужно оценить сверху количество особых вершин минимального и минимального по стягиванию /¿-связного графа.

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

Лемма 11. Пусть (7 — минимальный по стягиванию /¿-связный граф и > 2к. Рассмотрим произвольную вершину графа С и обозначим ее а. Тогда существует к-р аз дел я ю шее множество Т, содержащее а и по крайней мере одну из смежных с ней вершин, отделяющее компоненту, содержащую не более вершин.

Для изучения окрестности особой вершины рассматривается минимальная компонента, отделяемая /¿-разделяющим множеством, содержащим рассматриваемую особую вершину и вершину, с ней смежную. Благодаря лемме 11 рассмотрение таких компонент сводится к конечному разбору случаев. В первой главе также доказывается, что в случае, если какое-либо к-разделяющее множество, содержащее рассматриваемую вершину и смежную с ней, отделяет компоненту не более чем из двух вершин, то рассматриваемая вершина не может быть особой.

С помощью этой леммы доказывается следующая теорема.

Теорема 5. В минимальных и минимальных по стягиванию 6-связных графах особых вершин не существует.

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

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

В четвертой главе изучаются вершины, находящиеся на расстоянии 1 и 2 от особой вершины, содержащейся, вместе с вершиной с ней смежной, только в /с-разделяющих множествах, отделяющих компоненту из 4 вершин.

В пятой главе доказываются нижние оценки на с^ при к = 5,6, 7,8, 9,10. Для доказательства оценок в случаях 7, 8, 9,10 доказываются следующие существенные структурные леммы.

Лемма 29. Пусть С — минимальный и минимальный относительно стягивания /с-связный граф, где к Е {7, 8} и > 2к. Тогда количество особых вершин графа С не превосходит количества вершин степени к, смежных как минимум с двумя вершинами степени к.

Лемма 30. Пусть С — минимальный и минимальный относительно стягивания /с-связный граф, где к £ {9,10} и |С?| > 2к. Обозначим через 5о множество всех особых вершин графа С и через 62 — множество вершин степени к, смежных хотя бы с шестью вершинами степени к. Тогда 4|1 > №1

Теорема 8. Выполнены следующие неравенства: > | и с^ > где к = 6,7,8,9,10.

В шестой главе строятся три серии минимальных и минимальных по стягиванию /с-связных графов, отдельно для 5, четного и нечетного к. С помощью построеных графов доказываются верхние оценки для с^. Теорема 10. Выполнено неравенство С5 <

Теорема 12. Предположим, что к > 6 — нечетное число и к = 2£ + 3. Тогда выполнено неравенство с^ <

Теорема 14. Предположим, что к > 6 — четное число и к = 2£. Тогда а/З 1 о«2 ул , 1 о выполнено неравенство < 18€з142^+2б •

Таким образом, для к = 5,6,7,8,9,10 в пятой и шестой главах получены следующие оценки: | < с5 < Ц, \ < с<з < Ц, \ < с7 < \ < с8 < 46

7 — 0 ^ 22' 2 — ^ ^ 31' 2 — ^ 45' 2 — ^ 73' 401 14' 2 — " 665'

1 ^ ^ 9 1 / /401 9 Ь Й) < 9 ^ Сю <

1. K.Ando, A Local structure theorem on 5-connected graphs, J. Graph Theory 60 (2009), 99-129.

2. K.Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math 293 (2005), 61—72.

3. K.Ando, A.Kaneko, K.Kawarabayashi, Vertices of degree 7 in a contraction-critical 7-connected graph, preprint.

4. K. Ando, A. Kaneko, K. Kawarabayashi, Vertices of degree 6 in a contraction critically 6-connected graphs, Discrete Mathematics 273 (2003) 55-69.

5. K.Ando, K.Kawarabayashi, and A.Kaneko, Vertices of degree 5 in a contraction critically 5-connected graphs, Graphs Combin 21 (2005), 27—37.

6. К.Берж, Теория графов и ее применения Москва, Иностранная литература, 1962. (Перевод с французского. С.Berge, Théorie des graphes et ses applications Dunod, Paris, 1958.)

7. Y.Egawa, Contractible edges in n-connected graphs with minimum degree greater than or equal to f, Graphs Combin. 7 (1991), 15-21.

8. M.Fontet, Graphes 4-essentiels, C. R. Acad. Se. Paris, t. 287, serie A (1978), 289-290.

9. R.Halin, A theorem on n-connected graphs J. Comb. Theory 7 (1969), 150154.

10. R. Halin, On the structure of n-connected graphs In: Recent Progress in Combinatorics (ed: W. T. Tutte), Academic Press, London New York, 1969, p. 91-102.

11. Ф.Харари, Теория графов. Москва, "Мир 1973. (Перевод с английского. F. Harary, Graph theory, 1969.)

12. S.Hedetniemi, Characterizations and constructions of minimally 2-connected graphs and minimally strong digraphs, In: „Proc. Second Louisiana Conf. on Combinatorics, Graph Theory and Computing, 1971", Utilitas Mathematica, Winnipeg, pp. 257-282.

13. F.Go"ring, Short proof of Menger's theorem, Discrete Math. 219 (2000), no. 1-3, p 295-296.

14. Д.В.Карпов, А.В.Пастор, О структуре k-связного графа, Записки научных семинаров ПОМИ, 266 (2000), 76-106.

15. M.Kriesell, A degree sum condition for the existence of a contractible edge in a k-connected graph, J. Combin. Theory Ser.B 82 (1) (2001), 81-101.

16. T.Li, J.Su, The new lower bound of the number of vertices of degree 5 in contraction critical 5-connected graphs, Graphs Combin. 26 (2010), no. 3, 395—406.

17. M.Li, X.Yuan, J.Su, The number of vertices of degree 7 in a contraction-critical 7-connected graph, Discrete Mathematics 308 (2008), 6262-6268.

18. W.Mader, Ecken Vom Gard n in minimalen n-fach zusammenhangenden Graphen. (German), Arch.Math. (Basel), 23 (1972), 219-224.

19. W.Mader, Generalizations of critical connectivity of graphs. Discrete Mathematics 72 (1988), 267-283

20. W.Mader, Zur Struktur minimal n-fach zusammenhEangender Graphen. (German) Abh. Math. Sem. Univ. (Hamburg) 49 (1979), 49-69.

21. N.Martinov, A recursive characterization of the 4-connected graphs, Discrete Mathematics 84 (1990), 105-108.

22. K.Menger, Zur allgemeinen Kurventheorie, Fund. Math. 10 (1927), 96-115.

23. С.А.Образцова, О локальной структуре 5 и 6-связных графов, Записки научных семинаров ПОМИ, 381 (2010), 88-96.

24. С.А.Образцова, А.В.Пастор О локальной структуре 7 и 8-связных графов, Записки научных семинаров ПОМИ, 381 (2010), 97-111.

25. С.А.Образцова, А.В.Пастор, О вершинах степени к минимальных и минимальных относительно стягивания к-связных графов: верхние оценки, ПОМИ препринт, 5/2011.

26. С.А.Образцова, О локальной структуре 9 и 10-связных графов, ПОМИ препринт, 6/2011

27. О. Оре, Теория графов. Москва, "Наука 1968. (Перевод с английского. О. Ore, Theory of graphs, 1962.)

28. C.Qin, X.Yuan, J.Su, Some properties of contraction-critical 5-connected graphs, Discrete Mathematics 308 (2008), 5742-5756.

29. C.Qin, X.Yuan, J.Su, Triangles in contraction critical 5-connected graphs, Australas. J. Combin. 33 (2005), 139-146.

30. P. J.Slater, A classification of 4~connected graphs, J. of Combinatorial Theory 17 (1974), 261-289.

31. P.J.Slater, Soldering and point splitting, J. of Combinatorial Theory 24 (1978), 338-343.

32. J.Su, Vertices of degree 5 in contraction critical 5-connected graphs, J. Guangxi Normal Univ. 17 (3) (1997), 12-16 (in Chinese).

33. C.Thomassen, N on-separating cycles in k-connected graphs, J. Graph Theory 5 (1981), 351-354.

34. У. Татт, Теория графов Москва, Мир, 1988. (Перевод с английского. W.T.Tutte, Graph Theory Enciclopedia of Mathematics and Its Applications, vol. 21, 1984.)

35. W.T.Tutte, A theory of3-connected graphs. Indag. Math. 23 (1961), 441-455.

36. W.T.Tutte, Connectivity in graphs. Toronto, Univ. of Toronto Press, 1966.

37. X.Yuan, The contractible edges of 5-connected graphs, J. Guangxi Normal University, 14 (3) (1994) 30-32 (in Chinese).

38. X.Yuan, J.Su, Contractible Edges in 7-Connected Graphs, Graphs and Combinatorics 21 (2005), 445-457.