Тривиально идеальный граф

В теории графов тривиально совершенный граф — это граф со свойством, что в каждом из его индуцированных подграфов размер максимального независимого множества равен числу максимальных клик . ^[1] Тривиально совершенные графы были впервые изучены (Wolk 1962, 1965), но были названы Golumbic (1978); Golumbic пишет, что «название было выбрано, поскольку тривиально показать, что такой граф совершенен ». Тривиально совершенные графы также известны как графы сравнимости деревьев , ^[2] древовидные графы сравнимости , ^[3] и квазипороговые графы . ^[4]

Эквивалентные характеристики

Тривиально совершенные графы имеют несколько других эквивалентных характеристик:

Они являются графами сравнимости теоретико -порядковых деревьев . То есть, пусть $T$ — частичный порядок , такой что для каждого $t \in T$ множество ${s \in T : s < t}$ вполне упорядочено отношением < $,$ а также $T$ обладает минимальным элементом $r$ . Тогда граф сравнимости T $является$ тривиально совершенным, и каждый тривиально совершенный граф может быть сформирован таким образом. ^[5]
Это графы, которые не имеют $графа$ путей $P4$ или графа циклов $C4$ $в$ качестве индуцированных подграфов . ^[6]
Это графы, в которых каждый связный индуцированный подграф содержит универсальную вершину . ^[7]
Это графики, которые можно представить как графики интервалов для набора вложенных интервалов . Набор интервалов является вложенным, если для каждых двух интервалов в наборе либо два не пересекаются, либо один содержит другой. ^[8]
Это графы, которые являются как хордовыми , так и кографами . ^[9] Это следует из характеристики хордовых графов как графов без индуцированных циклов длины больше трех, а кографов как графов без индуцированных путей на четырех вершинах ( $P 4$ ).
Это графы, которые одновременно являются кографами и интервальными графами. ^[9]
Это графы, которые могут быть сформированы, начиная с графов с одной вершиной, с помощью двух операций: несвязного объединения двух меньших тривиально совершенных графов и добавления новой вершины, смежной со всеми вершинами меньшего тривиально совершенного графа. ^[10] Эти операции соответствуют в базовом лесу формированию нового леса путем несвязного объединения двух меньших лесов и формированию дерева путем соединения нового корневого узла с корнями всех деревьев в лесу.
Это графы, в которых для каждого ребра $uv$ окрестности u и $v$ (включая сами $u$ и $v ) являются вложенными: одна окрестность$ $должна$ быть подмножеством другой. ^[11]
Это графы перестановок, определенные из перестановок, сортируемых стеком . ^[12]
Это графы, обладающие тем свойством, что в каждом из его индуцированных подграфов число кликовых покрытий равно числу максимальных клик . ^[13]
Это графы, обладающие тем свойством, что в каждом из его индуцированных подграфов число клик равно псевдочислу Гранди. ^[13]
Это графы, обладающие тем свойством, что в каждом из его индуцированных подграфов хроматическое число равно псевдочислу Гранди. ^[13]

Связанные классы графов

Из эквивалентных характеристик тривиально совершенных графов следует, что каждый тривиально совершенный граф является также кографом , хордовым графом , птолемеевым графом , интервальным графом и совершенным графом .

Пороговые графы — это как раз те графы, которые сами по себе являются тривиально совершенными и являются дополнениями тривиально совершенных графов (котривиально совершенными графами). ^[14]

Графики ветряных мельниц тривиально идеальны.

Признание

Чу (2008) описывает простой алгоритм линейного времени для распознавания тривиально совершенных графов, основанный на лексикографическом поиске в ширину . Всякий раз, когда алгоритм LexBFS удаляет вершину $v$ из первого набора в своей очереди, алгоритм проверяет, принадлежат ли все оставшиеся соседи $v тому же набору; если нет, то из$ $v$ можно построить один из запрещенных индуцированных подграфов . Если эта проверка успешна для каждого $v$ , то граф тривиально совершенен. Алгоритм также можно модифицировать для проверки того, является ли граф дополнительным графом тривиально совершенного графа, за линейное время.

Определение того, находится ли общий граф на расстоянии $k$ удалений ребер от тривиально совершенного графа , является NP-полной задачей ^[15], поддается фиксированному параметрическому решению ^[16] и может быть решена за время $O (2,45 k (m + n))$ ^[17] .

Примечания

^ Брандштедт, Le & Spinrad (1999), определение 2.6.2, стр.34; Голуббик (1978).
^ Волк (1962); Волк (1965).
^ Доннелли и Айзек (1999).
^ Янь, Чэнь и Чан (1996).
^ Брандштедт, Ле и Спинрад (1999), теорема 6.6.1, с. 99; Голумбик (1978), следствие 4.
^ Brandstädt, Le & Spinrad (1999), теорема 6.6.1, стр. 99; Golumbic (1978), теорема 2. Wolk (1962) и Wolk (1965) доказали это для графов сравнимости корневых лесов.
^ Волк (1962).
^ Брандштедт, Le & Spinrad (1999), стр. 51.
^ ab Brandstädt, Le & Spinrad (1999), стр. 248; Ян, Чен и Чанг (1996), теорема 3.
^ Ян, Чэнь и Чан (1996); Гурски (2006).
^ Ян, Чен и Чан (1996), теорема 3.
^ Ротем (1981).
^ abc Рубио-Монтьель (2015).
^ Брандштедт, Ле и Спинрад (1999), теорема 6.6.3, с. 100; Голумбик (1978), следствие 5.
^ Шаран (2002).
^ Цай (1996).
^ Настос и Гао (2010).

Ссылки

Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: Обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
Cai, L. (1996), «Распознаваемость задач модификации графов для наследственных свойств с фиксированными параметрами», Information Processing Letters , 58 (4): 171–176, doi :10.1016/0020-0190(96)00050-6.
Чу, Фрэнк Пок Мэн (2008), «Простой алгоритм на основе LBFS с линейным временем сертификации для распознавания тривиально совершенных графов и их дополнений», Information Processing Letters , 107 (1): 7–12, doi :10.1016/j.ipl.2007.12.009.
Доннелли, Сэм; Айзек, Гарт (1999), «Гамильтоновы мощности в пороговых и древовидных графах сравнимости», Дискретная математика , 202 (1–3): 33–44, doi : 10.1016/S0012-365X(98)00346-X
Golumbic, Martin Charles (1978), «Тривиально совершенные графы», Discrete Mathematics , 24 (1): 105–107, doi :10.1016/0012-365X(78)90178-4.
Гурски, Франк (2006), «Характеристики для ко-графов, определяемых ограниченными операциями NLC-ширины или кликовой ширины», Дискретная математика , 306 (2): 271–277, doi :10.1016/j.disc.2005.11.014.
Nastos, James; Gao, Yong (2010), "Новая стратегия ветвления для задач модификации параметризованных графов", в Wu, Weili; Daescu, Ovidiu (ред.), Combinatory Optimization and Applications – 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, 18–20 декабря 2010 г., Proceedings, Часть II , Lecture Notes in Computer Science, т. 6509, Springer, стр. 332–346, arXiv : 1006.3020 , doi :10.1007/978-3-642-17461-2_27
Ротем, Д. (1981), «Стек-сортируемые перестановки», Дискретная математика , 33 (2): 185–196, doi :10.1016/0012-365X(81)90165-5, MR 0599081.
Рубио-Монтьель, К. (2015), «Новая характеристика тривиально совершенных графов», Электронный журнал теории графов и приложений , 3 (1): 22–26, doi : 10.5614/ejgta.2015.3.1.3.
Шаран, Родед (2002), «Проблемы модификации графов и их применение в геномных исследованиях», докторская диссертация, Тель-Авивский университет.
Волк, Э.С. (1962), «Граф сравнимости дерева», Труды Американского математического общества , 13 (5-е изд.): 789–795, doi : 10.1090/S0002-9939-1962-0172273-0.
Волк, Э.С. (1965), «Заметка о графе сравнимости дерева», Труды Американского математического общества , 16 (1-е изд.): 17–20, doi : 10.1090/S0002-9939-1965-0172274-5.
Ян, Джинг-Хо; Чен, Джер-Джонг; Чанг, Джерард Дж. (1996), «Квазипогороговые графики», Дискретная прикладная математика , 69 (3): 247–255, doi :10.1016/0166-218X(96)00094-7.

Внешние ссылки

«Тривиально совершенные графы», Информационная система по классам графов и их включениям