Jump to content

Universal graph: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
m [Pu331]+: arxiv, issue, doi.
Line 18: Line 18:
| volume = 1973
| volume = 1973
| pages = 319–326
| pages = 319–326
⚫
| doi = 10.1007/BF00052907
| id = {{arxiv|archive = math.LO|id = 9409206}}
| arxiv = archive = math.LO/id = 9409206
⚫
| doi = 10.1007/BF00052907}}</ref>
| issue = 4}}</ref>
<ref>{{cite journal
<ref>{{cite journal
| author = Cherlin, Greg; Shelah, Saharon; Shi, Niandong
| author = Cherlin, Greg; Shelah, Saharon; Shi, Niandong
Line 26: Line 27:
| volume = 22
| volume = 22
| year = 1999
| year = 1999
| pages = 454–491
| pages = 454–491
⚫
| doi = 10.1006/aama.1998.0641
| id = {{arxiv|archive = math.LO|id = 9809202}}
| arxiv = archive = math.LO/id = 9809202
⚫
| doi = 10.1006/aama.1998.0641}}</ref>
| issue = 4}}</ref>
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''.
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''.


Line 39: Line 41:
| year = 1985
| year = 1985
| pages = 238–249
| pages = 238–249
| doi = 10.1016/0743-7315(85)90026-7}}</ref>
| doi = 10.1016/0743-7315(85)90026-7
| issue = 3}}</ref>
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''-node trees with only ''n''&nbsp;vertices and O(''n''&nbsp;log&nbsp;''n'') edges, and that this is optimal.<ref>{{cite journal|first1=F. R. K.|last1=Chung|author1-link=Fan Chung|first2=R. L.|last2=Graham|author2-link=Ronald Graham|title=On universal graphs for spanning trees|journal=Journal of the London Mathematical Society|volume=27|year=1983|pages=203–211|url=http://www.math.ucsd.edu/~fan/mypaps/fanpap/35universal.pdf}}.</ref> A construction based on the [[planar separator theorem]] can be used to show that ''n''-vertex [[planar graph]]s have universal graphs with O(''n''<sup>3/2</sup>) edges, and that bounded-degree planar graphs have universal graphs with O(''n''&nbsp;log&nbsp;''n'') edges.<ref>{{Cite book
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''-node trees with only ''n''&nbsp;vertices and O(''n''&nbsp;log&nbsp;''n'') edges, and that this is optimal.<ref>{{cite journal|first1=F. R. K.|last1=Chung|author1-link=Fan Chung|first2=R. L.|last2=Graham|author2-link=Ronald Graham|title=On universal graphs for spanning trees|journal=Journal of the London Mathematical Society|volume=27|year=1983|pages=203–211|url=http://www.math.ucsd.edu/~fan/mypaps/fanpap/35universal.pdf|doi=10.1112/jlms/s2-27.2.203|issue=2}}.</ref> A construction based on the [[planar separator theorem]] can be used to show that ''n''-vertex [[planar graph]]s have universal graphs with O(''n''<sup>3/2</sup>) edges, and that bounded-degree planar graphs have universal graphs with O(''n''&nbsp;log&nbsp;''n'') edges.<ref>{{Cite book
| last1 = Babai | first1 = L. | author1-link = László Babai
| last1 = Babai | first1 = L. | author1-link = László Babai
| last2 = Chung | first2 = F. R. K. | author2-link = Fan Chung
| last2 = Chung | first2 = F. R. K. | author2-link = Fan Chung
Line 65: Line 68:
| title = Universal graphs for bounded-degree trees and planar graphs
| title = Universal graphs for bounded-degree trees and planar graphs
| volume = 2
| volume = 2
| year = 1989}}</ref><ref>{{Cite book
| year = 1989
| issue = 2}}</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

Revision as of 19:56, 6 April 2011

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. However it is not the smallest such graph: it is known that there is a universal graph for n-node 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] 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.[10]

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

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. Holt, Reinhart, and Winston. pp. 83–85. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  3. ^ Goldstern, Martin; Kojman, Menachem (1996). "Universal arrow-free graphs". Acta Math. Hungar. 1973 (4): 319–326. arXiv:= math.LO/id = 9409206 archive = math.LO/id = 9409206. doi:10.1007/BF00052907. {{cite journal}}: Check |arxiv= value (help)CS1 maint: multiple names: authors list (link)
  4. ^ Cherlin, Greg; Shelah, Saharon; Shi, Niandong (1999). "Universal graphs with forbidden subgraphs and algebraic closure". Advances in Applied Math. 22 (4): 454–491. arXiv:= math.LO/id = 9809202 archive = math.LO/id = 9809202. doi:10.1006/aama.1998.0641. {{cite journal}}: Check |arxiv= value (help)CS1 maint: multiple names: authors list (link)
  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" (PDF). Journal of the London Mathematical Society. 27 (2): 203–211. doi:10.1112/jlms/s2-27.2.203..
  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.
  8. ^ 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 (2): 145. 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; Schrijver, Alexander (eds.). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics. Vol. 9. Springer-Verlag. pp. 17–34. ISBN 9780387526850.
  10. ^ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Universal_graph&oldid=422744870"