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 a subgraph. Universal graphs of this type were first constructed by R. Rado (1964; 1967). Recent work (e.g. see Goldstern and Kojman 1994) 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 (Wu 1985) 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
- Goldstern, Martin; Kojman, Menachem (1994). "Universal bridge-free graphs". arXiv:math.LO/9409206.
- Rado, R. (1964). "Universal graphs and universal functions". Acta Arithmetica 9: 331–340.
- Rado, R. (1967). "Universal graphs". A Seminar in Graph Theory: 83–85, Holt, Reinhart, and Winston.
- Wu, A. Y. (1985). "Embedding of tree networks into hypercubes". Journal of Parallel and Distributed Computing 2: 238–249.
