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

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

Эта диссертация посвящена изучению понятия вершинной связности, которое является одним из естественных обобщений понятия связности и, вследствие этого, имеет большое теоретическое и практическое значение. Многие практические задачи, в частности, имеющие отношение к надежности различных систем связи и транспортных сетей, могут быть сформулированы в терминах вершинной связности подходящих графов. Некоторые примеры использования вершинной связности можно найти в книге [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, Theorie 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), 150 154.

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.