Універсальна вершина

Універсальна вершина — це вершина неорієнтованого графа, яка суміжна всім іншим вершинам графа. Вона може також називатися домінівною вершиною, оскільки вона утворює одноелементну домінівну множину в графі.

Граф, який містить універсальну вершину, можна також назвати конусом. У цьому контексті універсальну вершину називають апексом конуса^[1], однак це конфліктує з термінологією верхівкових графів, в яких іноді апексом називають вершину, видалення якої робить граф планарним.

У спеціальних сімействах графів

Зірки — це дерева, які мають універсальну вершину і можуть бути побудовані шляхом додавання універсальної вершини в незалежну множину. Колеса, аналогічно, можна утворити шляхом додавання універсальної вершини в цикл^[2]. У геометрії тривимірні піраміди мають колеса як кістяки, а більш загальні графи будь-якої піраміди в просторі будь-якої розмірності мають універсальну вершину як вершину (апекс) піраміди.

Тривіально досконалі графи (графи порівнянності дерев з теорії множин) завжди містять універсальну вершину, а саме, корінь дерева, і можуть бути описані як графи, в яких будь-який породжений підграф містить універсальну вершину^[3]. Досконалі порогові графи утворюють підклас тривіально досконалих графів, так що вони містять універсальну вершину. Їх можна визначити як графи, які можна утворити шляхом повторюваного додавання або універсальної вершини, або ізольованої вершини (тобто вершини без ребер)^[4].

Будь-який граф з універсальною вершиною розбірний і майже всі розбиранні графи мають універсальну вершину^[5].

Інші властивості

У графі з $n$ вершинами універсальна вершина — це вершина, степінь якої в дорівнює $n - 1$ . Тому, подібно до розщепних графів, графи з універсальною вершиною можна розпізнати чисто за їхньою послідовністю степенів без перегляду структури графів.

Див. також

Універсальний граф

Примітки

↑ Larrión, de Mello, Morgana, Neumann-Lara, Pizaña, 2004, с. 183–191.
↑ Bonato, 2008, с. 7.
↑ Wolk, 1962, с. 789–795.
↑ Chvátal, Hammer, 1977, с. 145–162.
↑ Bonato, Kemkes, Prałat, 2012, с. 1652–1657.

Література

Larrión F., de Mello C. P., Morgana A., Neumann-Lara V., Pizaña M. A. The clique operator on cographs and serial graphs // Discrete Mathematics. — 2004. — Т. 282, вип. 1-3. — С. 183–191. — DOI:10.1016/j.disc.2003.10.023.
Anthony Bonato. A course on the web graph. — Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS, 2008. — Т. 89. — С. 7. — (Graduate Studies in Mathematics) — ISBN 978-0-8218-4467-0. — DOI:10.1090/gsm/089.
Wolk E. S. The comparability graph of a tree // Proceedings of the American Mathematical Society. — 1962. — Т. 13. — С. 789–795. — DOI:10.2307/2034179.
Václav Chvátal, Peter Ladislaw Hammer. Aggregation of inequalities in integer programming // Studies in Integer Programming (Proc. Worksh. Bonn 1975) / Hammer P. L., Johnson E. L., Korte B. H., Nemhauser G. L. — Amsterdam : North-Holland, 1977. — Т. 1. — С. 145–162. — (Annals of Discrete Mathematics)
Anthony Bonato, Graeme Kemkes, Paweł Prałat. Almost all cop-win graphs contain a universal vertex // Discrete Mathematics. — 2012. — Т. 312, вип. 10. — С. 1652–1657. — DOI:10.1016/j.disc.2012.02.018.