Universal graph: Difference between revisions

Content deleted Content added

Inline

Revision as of 18:51, 22 February 2008

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.

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

[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: 319–326. arXiv:math.LO/9409206.{{cite journal}}: 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: 454–491. arXiv:math.LO/9809202.{{cite journal}}: 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: 238–249.

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
-In [[mathematics]], a '''universal graph''' is an infinite [[Graph (mathematics)|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''.
+In [[mathematics]], a '''universal graph''' is an infinite [[Graph (mathematics)|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<ref>{{cite journal
-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]].
-== References ==
-*{{cite journal
-  | author = Goldstern, Martin; Kojman, Menachem
-  | title = Universal bridge-free graphs
-  | year = 1994
-  | id = {{arxiv|archive = math.LO|id = 9409206}}}}
-*{{cite journal
   | author = Rado, R.
   | title = Universal graphs and universal functions
@@ Line 19: / Line 5: @@
   | volume = 9
   | year = 1964
-  | pages = 331–340}}
+  | pages = 331–340}}</ref><ref>{{cite conference
-*{{cite conference
   | author = Rado, R.
   | title = Universal graphs
@@ Line 27: / Line 11: @@
   | booktitle = A Seminar in Graph Theory
   | publisher = Holt, Reinhart, and Winston
+  | pages = 83–85}}</ref> and is now called the [[Rado graph]] or  random graph.  More recent work<ref>{{cite journal
-  | pages = 83–85}}
+  | author = Goldstern, Martin; Kojman, Menachem
+  | title = Universal arrow-free graphs
+  | year = 1996
+  | journal = Acta Math. Hungar.
+  | volume = 1973
+  | pages = 319-326
+  | id = {{arxiv|archive = math.LO|id = 9409206}}}}</ref>
+<ref>{{cite journal
+  | author = Cherlin, Greg; Shelah, Saharon; Shi, Niandong
+  | title =  Universal graphs with forbidden subgraphs and algebraic closure
+  | journal = Advances in Applied Math
+  | volume = 22
+  | year = 1999
+  | pages = 454-491
+  | id = {{arxiv|archive = math.LO|id = 9809202}}}}</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''.
+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]]<ref>
-*{{cite journal
+{{cite journal
   | author = Wu, A. Y.
   | title = Embedding of tree networks into hypercubes
@@ Line 35: / Line 36: @@
   | volume = 2
   | year = 1985
-  | pages = 238–249}}
+  | pages = 238–249}}</ref>
+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]].
+== References ==
+<references/>
 [[category:Graph families]]