Розщеплюваний граф

У теорії графів розщеплюваним графом називають граф, у якому вершини можна розділити на кліку і незалежну множину. Розщеплювані графи вперше вивчали Фелдес і Гаммер^[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]. Кохроматичне число^[en] розщеплюваних графів дорівнює 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 вершинами один до одного відповідають деяким сімействам Спернера^[en]. Скориставшись цим, він знайшов формулу числа (неізоморфних) розщеплюваних графів з n вершинами. Для малих значень n, починаючи від n = 1, ці числа дорівнюють

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, … послідовність A048194 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.

Це перерахування раніше довели Тишкевич та Черняк^[17].