Хорошо покрытый граф

Вершинное покрытие графа — это множество вершин графа такое, что у каждого ребра хотя бы один конец входит в покрытие. Покрытие минимально (неприводимо), если удаление любой вершины разрушает покрытие. Покрытие называется наименьшим, если нет другого покрытия графа с меньшим числом вершин. Хорошо покрытый граф — это граф, в котором любое минимальное покрытие является также наименьшим. В своей оригинальной статье Пламмер пишет[1], что определение хорошо покрытого графа «очевидно эквивалентно» свойству, что любые два минимальных покрытия имеют один и тот же размер.

Независимое множество графа — это множество вершин, в котором никакие две вершины не смежны. Если C — вершинное покрытие графа G, дополнение C должно быть независимым множеством, и наоборот. C является минимальным вершинным покрытием тогда и только тогда, когда его дополнение I является максимальным независимым множеством, и C является наименьшим вершинным покрытием тогда и только тогда, когда его дополнение является наибольшим независимым множеством. Таким образом, хорошо покрытый граф является, эквивалентно, графом, в котором каждое максимальное независимое множество является наибольшим.

В оригинальной статье о хорошо покрытых графах эти определения относились только к связным графам[1], хотя они имеют смысл и для несвязных графов. Некоторые более поздние авторы заменили требование связности более слабым требованием отсутствия изолированных вершин [2]. Как у связных хорошо покрытых графов, так и у хорошо покрытых графов без изолированных вершин не может быть существенных вершин, вершин, которые принадлежат каждому наименьшему вершинному покрытию [1]. Кроме того, любой хорошо покрытый граф является критическим графом для вершинных покрытий в том смысле, что удаление любой вершины v из графа даёт граф с меньшим по размеру наименьшим вершинным покрытием [1].

Комплекс независимости графа G — это симплициальный комплекс, имеющий симплекс для каждого независимого множества в G. Говорят, что симплициальный комплекс прост, если все его максимальные симплексы имеют одну мощность, так что хорошо покрытый граф эквивалентен графу с простым комплексом независимости[3].

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Неатакующие друг друга восемь ладей на шахматной доске. Если поместить меньше ладей, не атакующих друг друга, всегда найдётся место, куда поместить дополнительную ладью, при этом все ладьи не будут атаковать друг друга.

Граф-цикл длины четыре или пять является хорошо покрытым — в обоих случаях максимальное независимое множество имеет размер два. Цикл длиной семь и путь длиной три также хорошо покрыты. Любой полный граф является хорошо покрытым — любое максимальное независимое множество состоит из единственной вершины. Полный двудольный граф хорошо покрыт, если обе его доли имеют равное число вершин — для него имеется только два максимальных независимых множества. Ладейный граф хорошо покрыт — если поместить любое множество ладей на шахматной доске так, что никакие две ладьи не атакуют друг друга, всегда можно добавить ещё одну неатакующую ладью, пока на каждой строке и каждом столбце не окажется по ладье.

Если P является многоугольником или множеством точек, S является множеством открытых интервалов, имеющих вершины P в качестве конечных точек и не содержащих точки P внутри, а G является графом пересечений множества S (граф, имеющий вершины для каждого интервала из S и рёбра для каждой пары пересекающихся интервалов), тогда G является хорошо покрытым. Для этого случая любое максимальное независимое множество в G соответствует набору рёбер в триангуляции многоугольника P, а вычисление эйлеровой характеристики показывает, что любые две триангуляризации имеют одно и то же число рёбер[4].

Если G — какой-либо граф с n вершинами, корневым произведением G с графом, состоящим из одного ребра (то есть граф H, образованный добавлением n новых вершин к G, каждая со степенью единица и все соединены с разными вершинами, в G) является хорошо покрытым. Максимальное независимое множество в H должно состоять из произвольного независимого множества в G вместе с соседями, имеющими степень единица, из дополнительного множества. Таким образом, это множество имеет размер n[5]. Обобщённо, если дан любой граф G вместе с кликовым покрытием (разделение p вершин графа G на клики), граф G^p, образованный добавлением по вершине для каждой клики, является хорошо покрытым. Корневое произведение является специальным случаем этого построения, когда p состоит из n клик, содержащих по одной вершине[6]. Таким образом, любой граф является порождённым подграфом хорошо покрытого графа.

Фаварон (Favaron) определяет очень хорошо покрытый граф как хорошо покрытый граф (возможно, несвязный, но без изолированных вершин), в котором любое максимальное независимое множество (а потому также любое минимальное вершинное покрытие) содержит в точности половину вершин[2]. Это определение включает корневые произведения графа G и графа, состоящего из одного ребра. Сюда же входят, например, двудольные хорошо покрытые графы, которые изучали Равиндра и Берж[7][8] — в двудольном графе без изолированных вершин обе стороны любой доли образуют максимальные независимые множества (и минимальные покрытия вершин), так что если граф хорошо покрыт, обе стороны должны иметь равное число вершин. В хорошо покрытом графе с n вершинами размер максимального независимого множества не превосходит n/2, так что очень хорошо покрытые графы — это хорошо покрытые графы, в которых наибольшее независимое множество имеет максимально возможный для графов размер[8].

Двудольный граф G является хорошо покрытым тогда и только тогда, когда он является совершенным паросочетанием M со свойством, что для любого ребра uv из M порождённый подграф соседей u и v образует полный двудольный граф [7][9]. Характеризация в терминах паросочетаний может быть расширена с двудольных графов до очень хорошо покрытых графов — граф G является очень хорошо покрытым тогда и только тогда, когда граф имеет совершенное паросочетание M со следующими двумя свойствами:

1. Никакое ребро M не принадлежит треугольнику в G;
2. Если ребро M является центральным в пути, состоящим из трёх рёбер в G, то две конечных вершины пути должны быть смежными.

Однако если G очень хорошо покрыт, то любое совершенное паросочетание в G удовлетворяет этим свойствам[10].

Деревья являются специальным случаем двудольных графов, и проверка, является ли дерево хорошо покрытым, может рассматриваться как очень простой случай характеризации хорошо покрытых двудольных графов — если G является деревом с более чем двумя вершинами, оно хорошо покрыто тогда и только тогда, когда каждое нелистовое ребро дерева смежно в точности одному листу[7][9]. Та же самая характеризация применима к графам, которые локально подобны деревьям, в том смысле, что близкое окружение любой вершины ациклично — если граф имеет обхват восемь или более (так что для любой вершины v подграф из вершин на расстоянии три от v является ацикличным), то он хорошо покрыт тогда и только тогда, когда любая вершина со степенью большей двух имеет в точности одного соседа со степенью единица[11]. Тесно связанная, но более сложная характеризация применима к хорошо покрытым графам обхвата пять или больше[12][13].

Семь кубических 3-связных хорошо покрытых графов

Кубический 1-связный хорошо покрытый граф, образованный заменой каждого ребра шестирёберного пути одним из трёх фрагментов

Плосконосый двуклиноид, один из четырёх хорошо покрытых 4-связных 3-мерных симплициальных многогранников.

Кубические (3-регулярные) хорошо покрытые графы классифицированы — семейство состоит из семи 3-связных представителей и, кроме того, включает три бесконечных семейства кубических графов с меньшей связностью.

В эти семь 3-связных кубических хорошо покрытых графа входят полный граф K₄, графы треугольной и пятиугольной призм, граф Дюрера, коммунальный граф K_3,3, граф с восемью вершинами, полученный Y-Δ преобразованием из коммунального графа и обобщённый граф Петерсена G(7,2) с 14 вершинами[14]. Из этих графов первые четыре планарны, а потому только они являются также четырьмя кубическими полиэдральными графами (графами простых выпуклых многогранников), которые являются хорошо покрытыми. Четыре графа из семи (обе призмы, граф Дюрера и G(7,2)) являются обобщёнными графами Петерсена.

1- и 2-связные кубические хорошо покрытые графы образованы заменой вершин графа или цикла тремя фрагментами, которые Пламмер обозначил A, B и C[9]. Фрагменты A или B могут быть использованы для замены вершин цикла или внутренних вершин пути, в то время как фрагмент C используется для замены двух конечных вершин пути. Фрагмент A содержит мост, так что в результате замены некоторых вершин фрагментом A (остальные заменяются на B и C) получим вершинно 1-связный кубический хорошо покрытый граф. Все вершинно 1-связные кубические хорошо покрытые графы имеют такой вид, и все такие графы планарны[15].

Существует два типа вершинных 2-связных кубических хорошо покрытых графов. Одно из этих двух семейств образовано заменой вершин цикла фрагментами A и B, при этом по меньшей мере два фрагмента должны быть типа A. Граф этого типа планарен тогда и только тогда, когда он не содержит фрагментов типа B. Другое семейство образуется заменой вершин пути фрагментами типа B и C. Все такие графы планарны[15].

Рассматривая хорошее покрытие простых многогранников в трёхмерном пространстве, исследователи считают хорошо покрытыми симплициальные многогранники, или, что эквивалентно, хорошо покрытые максимальные планарные графы. Любой максимальный планарный граф с пятью и более вершинами имеет вершинную связность 3, 4 или 5[16]. Не существует хорошо покрытых 5-связных максимальных планарных графов и существует только четыре 4-связных хорошо покрытых максимальных планарных графа — графы правильного октаэдра, пятиугольной бипирамиды, плосконосого двуклиноида и неправильного многогранника (невыпуклого дельтаэдра) с 12 вершинами, 30 рёбрами и 20 треугольными гранями. Однако существует бесконечно много 3-связных хорошо покрытых максимальных планарных графов[17][18][19]. Например, хорошо покрытый 3-связный максимальный планарный граф может быть получен с помощью построения кликового покрытия [6] из любого максимального планарного графа с 3t вершинами, в котором имеется t несвязанных треугольных граней, путём добавления t новых вершин, по одному в каждой этой грани.

Проверка, содержит ли граф два максимальных независимых множества различных размеров, является NP-полной. То есть проверка, является ли граф хорошо покрытым, является coNP-полной задачей[20]. Хотя легко найти наибольшие независимые множества в графе, о котором известно, что он хорошо покрыт, для всех графов задача определения наибольшего независимого множества, как и проверка, что граф не является хорошо покрытым, NP-трудна[21].

В противоположность этому, проверить, что заданный граф G очень хорошо покрыт, можно за полиномиальное время. Чтобы сделать это, найдём подграф H графа G, состоящий из рёбер, удовлетворяющих двум свойствам паросочетаний в очень хорошо покрытом графе, а затем используем алгоритм нахождения совершенного покрытия для проверки, имеет ли H совершенное паросочетание[10]. Некоторые задачи, которые NP-полны для произвольных графов, такие как задача поиска гамильтонова пути, могут быть решены за полиномиальное время для любого хорошо покрытого графа[22].

Говорят, что граф однородно паросочетаем, если любое максимальное паросочетание является наибольшим. То есть он однородно паросочетаем, если его рёберный граф хорошо покрыт. Можно проверить, является ли рёберный граф, или, более обще, граф без клешней, хорошо покрытым за полиномиальное время[23].

Характеризация хорошо покрытых графов с обхватом пять или более и хорошо покрытых графов, являющихся 3-регулярными, также ведёт к эффективным полиномиальным алагоритмам распознавания таких графов[24].

• Claude Berge. Graph theory and algorithms (Proc. Sympos., Res. Inst. Electr. Comm., Tohoku Univ., Sendai, 1980). — Berlin: Springer, 1981. — Т. 108. — С. 108—123. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-10704-5_10.
• S. R. Campbell. Some results on cubic well-covered graphs. — Vanderbilt University, Department of Mathematics, 1987. Как цитировано у Пламмера (Plummer (1993)).
• S. R. Campbell, M. N. Ellingham, Gordon F. Royle. A characterisation of well-covered cubic graphs // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1993. — Т. 13. — С. 193—212.
• Stephen R. Campbell, Michael D. Plummer. On well-covered 3-polytopes // Ars Combinatoria. — 1988. — Т. 25, вып. A. — С. 215—242.
• Yair Caro, András Sebő, Michael Tarsi. Recognizing greedy structures // Journal of Algorithms. — 1996. — Т. 20, вып. 1. — С. 137—156. — doi:10.1006/jagm.1996.0006.
• Václav Chvátal, Peter J. Slater. Quo vadis, graph theory?. — Amsterdam: North-Holland, 1993. — Т. 55. — С. 179—181. — (Annals of Discrete Mathematics).
• David Cook II, Uwe Nagel. Cohen-Macaulay graphs and face vectors of flag complexes. — 2010. — arXiv:1003.4447.
• Anton Dochtermann, Alexander Engström. Algebraic properties of edge ideals via combinatorial topology // Electronic Journal of Combinatorics. — 2009. — Т. 16, вып. 2. — С. Research Paper 2.
• O. Favaron. Very well covered graphs // Discrete Mathematics. — 1982. — Т. 42, вып. 2—3. — С. 177—187. — doi:10.1016/0012-365X(82)90215-1.
• A. S. Finbow, B. L. Hartnell. A game related to covering by stars // Ars Combinatoria. — 1983. — Т. 16, вып. A. — С. 189—198.
• A. Finbow, B. Hartnell, R. Nowakowski. Well-dominated graphs: a collection of well-covered ones // Ars Combinatoria. — 1988. — Т. 25, вып. A. — С. 5—10.
• A. Finbow, B. Hartnell, R. J. Nowakowski. A characterization of well covered graphs of girth 5 or greater // Journal of Combinatorial Theory. — 1993. — Т. 57, вып. 1. — С. 44—68. — doi:10.1006/jctb.1993.1005.
• A. Finbow, B. Hartnell, R. Nowakowski, Michael D. Plummer. On well-covered triangulations. I // Discrete Applied Mathematics. — 2003. — Т. 132, вып. 1—3. — С. 97—108. — doi:10.1016/S0166-218X(03)00393-7.
• Arthur S. Finbow, Bert L. Hartnell, Richard J. Nowakowski, Michael D. Plummer. On well-covered triangulations. II // Discrete Applied Mathematics. — 2009. — Т. 157, вып. 13. — С. 2799—2817. — doi:10.1016/j.dam.2009.03.014.
• Arthur S. Finbow, Bert L. Hartnell, Richard J. Nowakowski, Michael D. Plummer. On well-covered triangulations. III // Discrete Applied Mathematics. — 2010. — Т. 158, вып. 8. — С. 894—912. — doi:10.1016/j.dam.2009.08.002.
• J. F. Fink, M. S. Jacobson, L. F. Kinch, J. Roberts. On graphs having domination number half their order // Period. Math. Hungar.. — 1985. — Т. 16, вып. 4. — С. 287—293. — doi:10.1007/BF01848079.
• Peter Greenberg. Piecewise SL₂Z geometry // Transactions of the American Mathematical Society. — 1993. — Т. 335, вып. 2. — С. 705—720. — doi:10.2307/2154401.
• M. Lesk, M. D. Plummer, W. R. Pulleyblank. Graph theory and combinatorics (Cambridge, 1983). — London: Academic Press, 1984. — С. 239—254.
• Michael D. Plummer. Some covering concepts in graphs // Journal of Combinatorial Theory. — 1970. — Т. 8. — С. 91—98. — doi:10.1016/S0021-9800(70)80011-4.
• Michael D. Plummer. Well-covered graphs: a survey // Quaestiones Mathematicae. — 1993. — Т. 16, вып. 3. — С. 253—287. — doi:10.1080/16073606.1993.9631737.
• Vijay Raghavan, Jeremy Spinrad. Robust algorithms for restricted domains // Journal of Algorithms. — 2003. — Т. 48, вып. 1. — С. 160—172. — doi:10.1016/S0196-6774(03)00048-8.
• G. Ravindra. Well-covered graphs // Journal of Combinatorics, Information and System Sciences. — 1977. — Т. 2, вып. 1. — С. 20—21.
• Ramesh S. Sankaranarayana, Lorna K. Stewart. Complexity results for well-covered graphs // Networks. — 1992. — Т. 22, вып. 3. — С. 247—262. — doi:10.1002/net.3230220304.
• J. Staples. On some subclasses of well-covered graphs. — Vanderbilt University, Department of Mathematics, 1975. Как процитировано у Пламмера (Plummer (1993)).
• David Tankus, Michael Tarsi. Well-covered claw-free graphs // Journal of Combinatorial Theory. — 1996. — Т. 66, вып. 2. — С. 293—302. — doi:10.1006/jctb.1996.0022.
• David Tankus, Michael Tarsi. The structure of well-covered graphs and the complexity of their recognition problems // Journal of Combinatorial Theory. — 1997. — Т. 69, вып. 2. — С. 230—233. — doi:10.1006/jctb.1996.1742.