Расщепляемый граф

В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество. Расщепляемые графы впервые изучали Фёлдес и Хаммер^[1][2], и независимо ввели Тышкевич и Черняк^[3][4].

Расщепляемый граф, разделённый на клику и независимое множество.

Расщепляемый граф может иметь несколько разложений на клику и независимое множество. Так, путь a-b-c является расщепляемым и может быть разбит тремя разными способами:

1. клика {a,b} и независимое множество {c}
2. клика {b,c} и независимое множество {a}
3. клика {b} и независимое множество {a,c}

Расщепляемые графы можно охарактеризовать в терминах их запрещённых подграфов — граф расщепляем в том и только в том случае, когда никакой порождённый подграф не является циклом с четырьмя или пятью вершинами, а также нет пары несвязных вершин (то есть дополнения цикла из 4 вершин)^[5][6].

Связь с другими семействами графов

По определению, класс расщепляемых графов замкнут по отношению к операции дополнения^[7]. Ещё одна характеристика расщепляемых графов, вовлекающая дополнение — это хордальные графы, дополнения которых также хордальны^[8]. Поскольку хордальные графы являются графами пересечений поддеревьев деревьев, расщепляемые графы являются графами пересечений различных подзвёзд звёзд^[9]. Почти все хордальные графы являются расщепляемыми графами. То есть, при стремлении n к бесконечности, частное от числа хордальных графов с n вершинами к числу разделяемых графов стремится к единице^[10].

Поскольку хордальные графы являются совершенными, то расщепляемые графы тоже совершенны. Двойные расщепляемые графы, семейство графов, полученных из расщепляемых графов удвоением числа вершин (так что клика даёт антисочетание — множество рёбер, находящихся на расстоянии не более 2 друг от друга, а независимое множество превращается в паросочетание), появляется как один из пяти основных классов совершенных графов, из которых можно построить все остальные в доказательство строгой теоремы о совершенных графах^[11].

Если граф и расщепляемый и интервальный, то его дополнение является и расщепляемым, и графом сравнимости, и наоборот. Расщепляемые графы сравнимости, а следовательно и расщепляемые интервальные графы, можно описать в терминах трёх запрещённых подграфов^[12]. Расщепляемые кографы — это в точности пороговые графы, а расщепляемые графы перестановки — это в точности интервальные графы, дополнения которых тоже являются интервальными^[13]. Кохроматическое число^[англ.] расщепляемых графов равно 2.

Максимальная клика и максимальное независимое множество

Пусть G — расщепляемый граф, разложенный на клику C и независимое множество I. Тогда любая максимальная клика в расщеплённом графе либо совпадает с C, либо является окрестностью вершины из I. Таким образом, в расщепляемом графе легко найти максимальную клику и, кроме того, максимальное независимое множество . В любом расщепляемом графе должно выполняться одно из следующих утверждений^[14]:

1. Существует вершина x в I, такая что C ∪ {x} является полным. В этом случае, C ∪ {x} — максимальная клика и I — максимальное независимое множество.
2. Существует вершина x в C, такая что I ∪ {x} — независимое множество. В этом случае I ∪ {x} — максимальное независимое множество и C — максимальная клика.
3. C является наибольшей кликой и I наибольшим независимым множеством. В этом случае G имеет единственное разложение (C, I) на клику и независимое множество, C является максимальной кликой, и I является максимальным независимым множеством.

Некоторые другие оптимизационные задачи, NP-полные на более общих семействах графов, включая раскраску, решаются просто на расщепляемых графах.

Последовательности степеней

Одно из замечательных свойств расщепляемых графов — это то, что они могут быть распознаны чисто по их последовательностям степеней вершин. Пусть d₁ ≥ d₂ ≥ … ≥ d_n — последовательность степеней вершин графа G и m — наибольшее значение i, для которого d_i ≥ i — 1. Тогда G является расщепляемым графом в том и только в том случае, когда

${\displaystyle \sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.}$

Если это выполняется, то m вершин с наибольшими степенями образуют максимальную клику G, а оставшиеся вершины дадут независимое множество^[15].

Подсчёт расщепляемых графов

Ройл^[16] показал, что расщепляемые графы с n вершинами один к одному соответствуют некоторым семействам Спернера^[англ.]. Используя этот факт он нашёл формулу числа (неизоморфных) расщепляемых графов с n вершинами. Для малых значений n, начиная с n = 1, эти числа равны

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, … последовательность A048194 в OEIS.

Это перечисление ранее доказали Тышкевич и Черняк^[17].