A universal graph is an infinite graph containing any finite (or no more than countable ) graph as a generated subgraph . A universal graph of this type was first constructed by R. Rado [1] [2] and this graph is now called the Rado graph or a random graph. More recent papers [3] [4] focus on universal graphs for a family of graphs F. That is, an infinite graph belonging to F containing all finite graphs of the family F. For example, Hanson graphs are universal in this sense for graphs without an i- click.
A universal graph for a family of graphs F can also be understood as a member of a sequence of finite graphs that contain all graphs in F. For example, any finite tree is a subgraph of a sufficiently large graph of a hypercube [5] , so we can say that a hypercube is a universal graph for trees. However, this is not the smallest such graph - it is known that there is a universal graph for trees with n vertices containing only n vertices and O ( n log n ) edges, and this graph is optimal [6] . A construction based on the planar decomposition theorem can be used to show that planar graphs with n vertices have universal graphs with O ( n 3/2 ) edges, and that planar graphs of a limited degree have universal graphs with O ( n log n ) the ribs [7] [8] [9] . Sumner’s hypothesis states that tournaments are universal for in the sense that any tournament with 2 n - 2 vertices contains any polytree with n vertices as a subtree [10] .
A family of graphs F has a universal graph of polynomial size containing any graph with n vertices as a generated subgraph if and only if it has in which vertices can be labeled with O (log n ) -bit lines such so that the algorithm can determine if vertices are adjacent by the labels of these vertices. If a graph of this type exists, the vertices of any graph in F can be labeled with the corresponding vertices of the universal graph, and vice versa, if the markup scheme exists, a universal graph containing all possible labels can be constructed [11] .
In old mathematical terminology, the phrase "universal graph" was sometimes used for a complete graph .
Notes
- ↑ Rado, 1964 , p. 331-340.
- ↑ Rado, 1967 , p. 83–85.
- ↑ Goldstern, Kojman, 1996 , p. 319–326.
- ↑ Cherlin, Shelah, Shi, 1999 , p. 454–491.
- ↑ Wu, 1985 , p. 238-249.
- ↑ Chung, Graham, 1983 , p. 203–211.
- ↑ Babai, Chung, Erdős, Graham, Spencer, 1982 , p. 21–26.
- ↑ Bhatt, Chung, Leighton, Rosenberg, 1989 , p. 145.
- ↑ Chung, 1990 , p. 17–34.
- ↑ Sumner's Universal Tournament Conjecture , Douglas B. West, retrieved 2010-09-17.
- ↑ Kannan, Naor, Rudich, 1992 , p. 596-603.
Literature
- FRK Chung, RL Graham. On universal graphs for spanning trees // Journal of the London Mathematical Society. - 1983 .-- T. 27 , no. 2 . - DOI : 10.1112 / jlms / s2-27.2.203 .
- R. Rado. Universal graphs and universal functions // Acta Arithmetica. - 1964 .-- T. 9 .
- 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. - T. 1973 , no. 4 . - DOI : 10.1007 / BF00052907 . - arXiv : math.LO / 9409206 .
- Greg Cherlin, Saharon Shelah, Niandong Shi. Universal graphs with forbidden subgraphs and algebraic closure // Advances in Applied Mathematics. - 1999. - T. 22 , no. 4 . - DOI : 10.1006 / aama.1998.0641 . - arXiv : math.LO / 9809202 .
- Ay wu. Embedding of tree networks into hypercubes // Journal of Parallel and Distributed Computing. - 1985. - T. 2 , no. 3 . - DOI : 10.1016 / 0743-7315 (85) 90026-7 .
- L. Babai , FRK Chung , P. Erdős , RL Graham , JH 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. - T. 12. - (Annals of Discrete Mathematics).
- Sandeep N. Bhatt, Fan RK Chung, FT Leighton, Arnold L. Rosenberg. Universal graphs for bounded-degree trees and planar graphs // SIAM Journal on Discrete Mathematics . - 1989.- T. 2 , no. 2 . - DOI : 10.1137 / 0402014 .
- Fan RK Chung. 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. - T. 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. - T. 5 , no. 4 . - DOI : 10.1137 / 0405049 .
Links
- The panarborial formula , "Theorem of the Day" regarding universal graphs for trees