Тривіально досконалий граф

Побудова тривіально досконалого графу зі вкладених інтервалів і з відношення досяжності в дереві

Тривіально досконалий граф — це граф із властивістю, що в кожному його породженому підграфі розмір найбільшої (за розміром) незалежної множини дорівнює числу найбільших клік[1][2]. Тривіально досконалі графи першим вивчав Волк[3][4], але назву дав Голумбік[2]. Голумбік писав, що «цю назву вибрано з огляду на тривіальність доведення, що такі графи є досконалими». Тривіально досконалі графи відомі також як графи порівнянності дерев[3][4], деревовидні графи порівнянності[5] і квазіпорогові графи[6].

Еквівалентні описи

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

• Вони є графами порівнянності дерев з теорії порядків^[en]. Тобто, нехай T — частковий порядок, такий, що для будь-якого t ∈ 'T' множина {s ∈ T : S < t} є цілком упорядкованою з відношенням < і T має найменший елемент r. Тоді граф порівнянності порядку T тривіально досконалий і будь-який тривіально досконалий граф можна сформувати таким способом[7][8].
• Вони є графами, що не містять шляху P₄ або циклу C₄ як породжених підграфів[7][9][10]
• Вони є графами, в яких кожен зв'язний породжений підграф містить універсальну вершину[3].
• Вони є графами, які можна подати як інтервальні графи множини вкладених проміжків. Множина проміжків має властивість вкладеності, якщо для будь-яких двох проміжків із множини вони або не перетинаються, або один з них міститься в іншому[11].
• Вони є графами, які одночасно є хордальними графами і кографами[12][13]. Це випливає з опису хордальних графів як графів без породжених циклів довжини чотири і більше і кографів як графів без породжених шляхів з чотирма вершинами (P₄).
• Це графи, які водночас є кографами й інтервальними графами[12][13].
• Вони є графами, які можна утворити, починаючи з графів з однією вершиною, за допомогою двох операцій — незв'язного об'єднання двох менших тривіально досконалих графів і додання нової вершини, суміжної всім вершинам меншого тривіально досконалого графу[6][14]. Ці операції відповідають утворенню нового лісу незв'язним об'єднанням двох менших лісів і утворенню дерева з'єднанням нового кореня з коренями всіх дерев лісу.
• Вони є графами, в яких для будь-якого ребра uv околи вершин u і v (включно з самими u і v) вкладені — один окіл має бути околом іншого[13].
• Вони є графами перестановки, визначеними зі сортованих у стеку перестановок^[en][15].
• Вони є графами з властивістю, що в кожному його породженому підграфі число клікового покриття дорівнює числу максимальних клік[16].
• Вони є графами з властивістю, що в кожному його породженому підграфі клікове число дорівнює псевдочислу Ґранді[16].
• Вони є графами з властивістю, що хроматичне число кожного його породженого підграфу дорівнює псевдочислу Ґранді[16].

Пов'язані класи графів

З еквівалентних описів тривіально досконалих графів випливає, що будь-який тривіально досконалий граф є також кографом, хордальним, птолемеєвим, інтервальним і досконалим графом.

Порогові графи — це точно ті графи, які є одночасно тривіально досконалими і є доповненням тривіально досконалих графів (тривіально досконалих кографів)[17][18].

Вітряки є тривіально досконалими.

Розпізнавання

Чу[19] описує простий алгоритм лінійного часу для розпізнавання тривіально досконалих графів, заснований на лексикографічному пошуку в ширину. Коли алгоритм LexBFS видаляє вершину v з першої множини в черзі, алгоритм перевіряє, що всі сусіди вершини v, що залишилися, належать тій самій множині. Якщо ні, один із заборонених породжених підграфів можна побудувати з v. Якщо перевірка успішна для всіх v, то граф тривіально досконалий. Алгоритм можна модифікувати для перевірки за лінійний час, чи є граф доповненням тривіально досконалого графу.

Визначення, чи стає граф загального вигляду після видалення k ребер тривіально досконалим графом, є NP-повною задачею[20], фіксовано-параметрично розв'язною[21], і її можна розв'язати за час O(2,45^k(m+n))[22].

Примітки

1. Brandstädt, Le, Spinrad, 1999, с. 34 визначення 2.6.2.
2. Golumbic, 1978.
3. Wolk, 1962.
4. Wolk, 1965.
5. Donnelly, Isaak, 1999.
6. Yan, Chen, Chang, 1996.
7. Brandstädt, Le, Spinrad, 1999, с. 99 теорема 6.6.1.
8. Golumbic, 1978, с. наслідок 4.
9. Golumbic, 1978, с. теорема 2.
10. Волк(Wolk, 1962)(Wolk, 1965) довів це для графів порівнянності кореневих лісів.
11. Brandstädt, Le, Spinrad, 1999, с. 51.
12. Brandstädt, Le, Spinrad, 1999, с. 248.
13. Yan, Chen, Chang, 1996, с. теорема 3.
14. Gurski, 2006.
15. Rotem, 1981.
16. Rubio-Montiel, (2015).
17. Brandstädt, Le, Spinrad, 1999, с. 100 теорема 6.6.3.
18. Golumbic, 1978, с. наслідок 5.
19. Chu, 2008.
20. Sharan, (2002).
21. Cai, (1996).
22. Nastos, Gao, 2010.

Література

• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X.
• Cai L. Fixed-parameter tractability of graph modification problems for hereditary properties // Information Processing Letters. — 1996. — Т. 58, вип. 4 (27 грудня). — С. 171–176. — DOI:10.1016/0020-0190(96)00050-6.
• Frank Pok Man Chu. A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements // Information Processing Letters. — 2008. — Т. 107, вип. 1 (27 грудня). — С. 7–12. — DOI:10.1016/j.ipl.2007.12.009.
• Sam Donnelly, Garth Isaak. Hamiltonian powers in threshold and arborescent comparability graphs // Discrete Mathematics. — 1999. — Т. 202, вип. 1—3 (27 грудня). — С. 33–44. — DOI:10.1016/S0012-365X(98)00346-X.
• Martin Charles Golumbic. Trivially perfect graphs // Discrete Mathematics. — 1978. — Т. 24, вип. 1 (27 грудня). — С. 105–107. — DOI:10.1016/0012-365X(78)90178-4.
• Frank Gurski. Characterizations for co-graphs defined by restricted NLC-width or clique-width operations // Discrete Mathematics. — 2006. — Т. 306, вип. 2 (27 грудня). — С. 271–277. — DOI:10.1016/j.disc.2005.11.014.
• James Nastos, Yong Gao. A Novel Branching Strategy for Parameterized Graph Modification Problems // Lecture Notes in Computer Science. — 2010. — Т. 6509 (27 грудня). — С. 332–346.
• Rotem D. Stack sortable permutations // Discrete Mathematics. — 1981. — Т. 33, вип. 2 (27 грудня). — С. 185–196. — DOI:10.1016/0012-365X(81)90165-5.
• Rubio-Montiel C. A new characterization of trivially perfect graphs // Electronic Journal of Graph Theory and Applications. — 2015. — Т. 3, вип. 1 (27 грудня). — С. 22–26. — DOI:10.5614/ejgta.2015.3.1.3.
• Roded Sharan. Graph modification problems and their applications to genomic research // PhD Thesis, Tel Aviv University. — 2002. — 27 грудня.
• Wolk E. S. The comparability graph of a tree // Proceedings of the American Mathematical Society. — 1962. — Т. 13, вип. 5 (27 грудня). — С. 789–795. — DOI:10.1090/S0002-9939-1962-0172273-0.
• Wolk E. S. A note on the comparability graph of a tree // Proceedings of the American Mathematical Society. — 1965. — Т. 16 (27 грудня). — С. 17–20. — DOI:10.1090/S0002-9939-1965-0172274-5.
• Jing-Ho Yan, Jer-Jeong Chen, Gerard J. Chang. Quasi-threshold graphs // Discrete Applied Mathematics. — 1996. — Т. 69, вип. 3 (27 грудня). — С. 247–255. — DOI:10.1016/0166-218X(96)00094-7.

Посилання

• Trivially perfect graphs, Information System on Graph Classes and their Inclusions, архів оригіналу за 26 серпня 2012, процитовано 24 червня 2021