Universal graph

From HandWiki

In mathematics, a universal graph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado[1][2] and is now called the Rado graph or random graph. More recent work[3] [4] has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.

A universal graph for a family F of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in F; for instance, every finite tree is a subgraph of a sufficiently large hypercube graph[5] so a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for n-vertex trees, with only n vertices and O(n log n) edges, and that this is optimal.[6] A construction based on the planar separator theorem can be used to show that n-vertex planar graphs have universal graphs with O(n3/2) edges, and that bounded-degree planar graphs have universal graphs with O(n log n) edges.[7][8][9] It is also possible to construct universal graphs for planar graphs that have n1+o(1) vertices.[10] Sumner's conjecture states that tournaments are universal for polytrees, in the sense that every tournament with 2n − 2 vertices contains every polytree with n vertices as a subgraph.[11]

A family F of graphs has a universal graph of polynomial size, containing every n-vertex graph as an induced subgraph, if and only if it has an adjacency labelling scheme in which vertices may be labeled by O(log n)-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in F may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label.[12]

In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph.

The notion of universal graph has been adapted and used for solving mean payoff games.[13]

References

  1. ↑ "Universal graphs and universal functions". Acta Arithmetica 9 (4): 331–340. 1964. doi:10.4064/aa-9-4-331-340. 
  2. ↑ "Universal graphs". Holt, Rinehart, and Winston. 1967. pp. 83–85. 
  3. ↑ Goldstern, Martin; Kojman, Menachem (1996). "Universal arrow-free graphs". Acta Mathematica Hungarica 1973 (4): 319–326. doi:10.1007/BF00052907. 
  4. ↑ Cherlin, Greg (1999). "Universal graphs with forbidden subgraphs and algebraic closure". Advances in Applied Mathematics 22 (4): 454–491. doi:10.1006/aama.1998.0641. 
  5. ↑ Wu, A. Y. (1985). "Embedding of tree networks into hypercubes". Journal of Parallel and Distributed Computing 2 (3): 238–249. doi:10.1016/0743-7315(85)90026-7. 
  6. ↑ Chung, F. R. K.; Graham, R. L. (1983). "On universal graphs for spanning trees". Journal of the London Mathematical Society 27 (2): 203–211. doi:10.1112/jlms/s2-27.2.203. http://www.math.ucsd.edu/~fan/mypaps/fanpap/35universal.pdf. .
  7. ↑ Rosa, Alexander; Sabidussi, Gert; Turgeon, Jean, eds (1982). "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. Annals of Discrete Mathematics. 12. pp. 21–26. http://renyi.hu/~p_erdos/1982-12.pdf. 
  8. ↑ Bhatt, Sandeep N. (1989). "Universal graphs for bounded-degree trees and planar graphs". SIAM Journal on Discrete Mathematics 2 (2): 145–155. doi:10.1137/0402014. 
  9. ↑ Chung, Fan R. K. (1990). "Separator theorems and their applications". in Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen et al.. Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics. 9. Springer-Verlag. pp. 17–34. ISBN 978-0-387-52685-0. https://archive.org/details/pathsflowsvlsila0000unse/page/17. 
  10. ↑ Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2021), "Adjacency Labelling for Planar Graphs (And Beyond)", Journal of the ACM 68 (6): 1–33, doi:10.1145/3477542 
  11. ↑ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
  12. ↑ Kannan, Sampath (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics 5 (4): 596–603, doi:10.1137/0405049 .
  13. ↑ Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (2018-07-27). "Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games". Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2333–2349. doi:10.1137/1.9781611975482.142. ISBN 978-1-61197-548-2. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Universal_graph&oldid=3012610"