Universal graph: Difference between revisions
m WP:CHECKWIKI error fixes + genfixes using AWB |
|||
| Line 66: | Line 66: | ||
| volume = 2 |
| volume = 2 |
||
| year = 1989 |
| year = 1989 |
||
| postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. --> |
| postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->}}.</ref><ref>{{Cite book |
||
| last = Chung | first = Fan R. K. | author-link = Fan Chung |
| last = Chung | first = Fan R. K. | author-link = Fan Chung |
||
| contribution = Separator theorems and their applications |
| contribution = Separator theorems and their applications |
||
| Line 86: | Line 86: | ||
{{reflist}} |
{{reflist}} |
||
{{DEFAULTSORT:Universal Graph}} |
|||
| ⚫ | |||
[[Category:Articles with inconsistent citation formats]] |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
[[es:Grafo universal]] |
[[es:Grafo universal]] |
||
Revision as of 12:44, 15 October 2010
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. 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.[6][7][8] 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.[9]
In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph.
References
- ^ Rado, R. (1964). "Universal graphs and universal functions". Acta Arithmetica. 9: 331–340.
- ^ Rado, R. (1967). "Universal graphs". A Seminar in Graph Theory. Holt, Reinhart, and Winston. pp. 83–85.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help) - ^ Goldstern, Martin; Kojman, Menachem (1996). "Universal arrow-free graphs". Acta Math. Hungar. 1973: 319–326. doi:10.1007/BF00052907. arXiv:math.LO/9409206.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ^ 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.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ^ 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.
- ^ Babai, L.; Chung, F. R. K.; Erdős, P.; Graham, R. L.; Spencer, J. H. (1982). "On graphs which contain all sparse graphs". In Rosa, Alexander; Sabidussi, Gert; Turgeon, Jean (eds.). Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday (PDF). Annals of Discrete Mathematics. Vol. 12. pp. 21–26.
- ^ Bhatt, Sandeep N.; Chung, Fan R. K.; Leighton, F. T.; Rosenberg, Arnold L. (1989). "Universal graphs for bounded-degree trees and planar graphs". SIAM Journal on Discrete Mathematics. 2: 145. doi:10.1137/0402014..
- ^ Chung, Fan R. K. (1990). "Separator theorems and their applications". In Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (eds.). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics. Vol. 9. Springer-Verlag. pp. 17–34. ISBN 9780387526850.
- ^ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.