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

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

Эквивалентные описания

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

• Они являются графами сравнимости деревьев из теории порядков. То есть пусть T — частичный порядок, такой, что для любого t ∈ T множество {s ∈ T : s < t} является вполне упорядоченным с отношением < и T обладает наименьшим элементом r. Тогда граф сравнимости порядка T тривиально совершенен и любой тривиально совершенный граф может быть сформирован таким образом.
• Они являются графами, не содержащими путь P4 или цикл C4 в качестве порождённых подграфов
• Они являются графами, в которых каждый связный порождённый подграф содержит универсальную вершину.
• Они являются графами, которые можно представить как интервальные графы множества вложенных промежутков. Множество промежутков имеет свойство вложенности, если для любых двух промежутков из множества они либо не пересекаются, либо один из них содержится в другом.
• Они являются графами, которые одновременно являются хордальными графами и кографами. Это следует из описания хордальных графов как графов без порождённых циклов длины четыре и больше и кографов как графов без порождённых путей с четырьмя вершинами (P4).
• Они являются графами, одновременно являющимися кографами и интервальными графами.
• Они являются графами, которые могут быть образованы, начиная с графов с одной вершиной, с помощью двух операций — несвязное объединение двух меньших тривиально совершенных графов и добавления новой вершины, смежной всем вершинам меньшего тривиально совершенного графа. Эти операции соответствуют образованию нового леса путём несвязного объединения двух меньших лесов и образованию дерева путём соединения нового корня с корнями всех деревьев леса.
• Они являются графами, в которых для любого ребра uv окрестности вершин u и v (включая сами u и v) вложены — одна окрестность должна быть окрестностью другой.
• Они являются графами перестановки, определёнными из сортируемых в стеке перестановок.
• Они являются графами со свойством, что в каждом его порождённом подграфе число кликового покрытия равно числу максимальных клик.
• Они являются графами со свойством, что в каждом его порождённом подграфе кликовое число равно псевдочислу Гранди.
• Они являются графами со свойством, что хроматическое число каждого его порождённого подграфа равно псевдочислу Гранди.

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

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

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

Мельницы являются тривиально совершенными.

Распознавание

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

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