Universal graph

From Wikipedia, the free encyclopedia

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 R. 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.

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.

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

[edit] References

  1. ^ Rado, R. (1964). "Universal graphs and universal functions". Acta Arithmetica 9: 331–340. 
  2. ^ Rado, R. (1967). "Universal graphs". A Seminar in Graph Theory: 83–85, Holt, Reinhart, and Winston. 
  3. ^ Goldstern, Martin; Kojman, Menachem (1996). "Universal arrow-free graphs". Acta Math. Hungar. 1973: 319-326. doi:10.1007/BF00052907. arXiv:math.LO/9409206. 
  4. ^ Cherlin, Greg; Shelah, Saharon; Shi, Niandong (1999). "Universal graphs with forbidden subgraphs and algebraic closure". Advances in Applied Math 22: 454-491. doi:10.1006/aama.1998.0641. arXiv:math.LO/9809202. 
  5. ^ Wu, A. Y. (1985). "Embedding of tree networks into hypercubes". Journal of Parallel and Distributed Computing 2: 238–249. doi:10.1016/0743-7315(85)90026-7.