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

Універса́льний граф — це нескінченний граф, що містить будь-який скінченний (або не більше ніж зліченний) граф як породжений підграф. Універсальний граф цього типу першим побудував Р. Радо^[1]^[2] і цей граф тепер називають графом Радо або випадковим графом. Свіжіші роботи^[3]^[4] фокусуються на універсальних графах для сімейства графів $F$ . Тобто нескінченний граф, що належить $F$ , який містить усі скінченні графи сімейства $F$ . Наприклад, графи Генсона є універсальними в цьому сенсі для графів без $i$ -клік.

Універсальний граф для сімейства графів $F$ можна також розуміти як член послідовності скінченних графів, які містять усі графи з $F$ . Наприклад, будь-яке скінченне дерево є підграфом достатньо великого графа гіперкуба^[5], так що можна сказати, що гіперкуб є універсальним графом для дерев. Однак це не найменший такий граф — відомо, що існує універсальний граф для дерев з $n$ вершинами, що містить всього $n$ вершин і $O(n log n)$ ребер, і цей граф оптимальний^[6]. Побудову, засновану на теоремі про планарне розбиття, можна використати, щоб показати, що планарні графи з $n$ вершинами мають універсальні графи з $O(n 3/2)$ ребрами, і що планарні графи обмеженого степеня мають універсальні графи з $O(n log n)$ ребрами^[7]^[8]^[9]. Гіпотеза Самнера стверджує, що турнір є універсальними для полідерев^[en] у тому сенсі, що будь-який турнір з $2 n - 2$ вершинами містить будь-яке полідерево з $n$ вершинами як піддерево^[10].

Сімейство графів $F$ має універсальний граф поліноміального розміру, що містить будь-який граф з $n$ вершинами як породжений підграф, тоді й лише тоді, коли він має схему суміжної розмітки^[en], в якій вершини можна позначити $O (log n)$ -бітовими рядками так, що алгоритм може визначити, чи суміжні вершини, за мітками цих вершин. Якщо граф цього типу існує, вершини будь-якого графа в $F$ можна позначити мітками відповідних вершин універсального графа, і навпаки, якщо схема розмітки існує, можна побудувати універсальний граф, що містить усі можливі мітки^[11].

У старій математичній термінології фразу «універсальний граф» іноді використовували для повного графа.

Примітки

↑ Rado, 1964, с. 331–340.
↑ Rado, 1967, с. 83–85.
↑ Goldstern, Kojman, 1996, с. 319–326.
↑ Cherlin, Shelah, Shi, 1999, с. 454–491.
↑ Wu, 1985, с. 238–249.
↑ Chung, Graham, 1983, с. 203–211.
↑ Babai, Chung, Erdős, Graham, Spencer, 1982, с. 21–26.
↑ Bhatt, Chung, Leighton, Rosenberg, 1989, с. 145.
↑ Chung, 1990, с. 17–34.
↑ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
↑ Kannan, Naor, Rudich, 1992, с. 596–603.

Література

F. R. K. Chung^[en], R. L. Graham. On universal graphs for spanning trees // Journal of the London Mathematical Society. — 1983. — Т. 27, вип. 2 (28 червня). — DOI:10.1112/jlms/s2-27.2.203.
R. Rado. Universal graphs and universal functions // Acta Arithmetica. — 1964. — Т. 9 (28 червня).
R. Rado. Universal graphs // A Seminar in Graph Theory. — Holt, Rinehart, and Winston, 1967.
Martin Goldstern, Menachem Kojman. Universal arrow-free graphs // Acta Mathematica Hungarica. — 1996. — Т. 1973, вип. 4 (28 червня). — arXiv:math.LO/9409206. — DOI:10.1007/BF00052907.
Greg Cherlin, Saharon Shelah, Niandong Shi. Universal graphs with forbidden subgraphs and algebraic closure // Advances in Applied Mathematics. — 1999. — Т. 22, вип. 4 (28 червня). — arXiv:math.LO/9809202. — DOI:10.1006/aama.1998.0641.
A. Y. Wu. Embedding of tree networks into hypercubes // Journal of Parallel and Distributed Computing. — 1985. — Т. 2, вип. 3 (28 червня). — DOI:10.1016/0743-7315(85)90026-7.
L. Babai, F. R. K. Chung^[en], P. Erdős, R. L. Graham, J. H. Spencer. On graphs which contain all sparse graphs // Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday / Alexander Rosa, Gert Sabidussi, Jean Turgeon. — 1982. — Т. 12. — (Annals of Discrete Mathematics)
Sandeep N. Bhatt, Fan R. K. Chung^[en], F. T. Leighton, Arnold L. Rosenberg. Universal graphs for bounded-degree trees and planar graphs // SIAM Journal on Discrete Mathematics. — 1989. — Т. 2, вип. 2 (28 червня). — DOI:10.1137/0402014.
Fan R. K. Chung^[en]. Separator theorems and their applications // Paths, Flows, and VLSI-Layout / Bernhard Korte, László Lovász, Hans Jürgen Prömel, Alexander Schrijver. — Springer-Verlag, 1990. — Т. 9. — (Algorithms and Combinatorics) — ISBN 978-0-387-52685-0.
Sampath Kannan, Moni Naor, Steven Rudich. Implicit representation of graphs // SIAM Journal on Discrete Mathematics. — 1992. — Т. 5, вип. 4 (28 червня). — DOI:10.1137/0405049.

Посилання

The panarborial formula, «Theorem of the Day» concerning universal graphs for trees

[FOOTNOTERado1964331–340-1] Rado, 1964, с. 331–340.

[FOOTNOTERado196783–85-2] Rado, 1967, с. 83–85.

[FOOTNOTEGoldstern,_Kojman1996319–326-3] Goldstern, Kojman, 1996, с. 319–326.

[FOOTNOTECherlin,_Shelah,_Shi1999454–491-4] Cherlin, Shelah, Shi, 1999, с. 454–491.

[FOOTNOTEWu1985238–249-5] Wu, 1985, с. 238–249.

[FOOTNOTEChung,_Graham1983203–211-6] Chung, Graham, 1983, с. 203–211.

[FOOTNOTEBabai,_Chung,_Erdős,_Graham,_Spencer198221–26-7] Babai, Chung, Erdős, Graham, Spencer, 1982, с. 21–26.

[FOOTNOTEBhatt,_Chung,_Leighton,_Rosenberg1989145-8] Bhatt, Chung, Leighton, Rosenberg, 1989, с. 145.

[FOOTNOTEChung199017–34-9] Chung, 1990, с. 17–34.

[10] Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.

[FOOTNOTEKannan,_Naor,_Rudich1992596–603-11] Kannan, Naor, Rudich, 1992, с. 596–603.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]