Universal graph: Difference between revisions
imported>BagLuke Added illustration and description. |
imported>SchlurcherBot m Bot: http → https |
||
| Line 53: | Line 53: | ||
| doi = 10.1016/0743-7315(85)90026-7 | | doi = 10.1016/0743-7315(85)90026-7 | ||
| issue = 3 }}</ref> | | 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 {{mvar|n}}-vertex trees, with only {{mvar|n}} vertices and {{math|O(''n'' log ''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= | 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 {{mvar|n}}-vertex trees, with only {{mvar|n}} vertices and {{math|O(''n'' log ''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=https://www.math.ucsd.edu/~fan/mypaps/fanpap/35universal.pdf|doi=10.1112/jlms/s2-27.2.203|issue=2|mr=0692525|citeseerx=10.1.1.108.3415}}.</ref> A construction based on the [[planar separator theorem]] can be used to show that {{mvar|n}}-vertex [[planar graph]]s have universal graphs with {{math|O(''n''<sup>3/2</sup>)}} edges, and that bounded-degree planar graphs have universal graphs with {{math|O(''n'' log ''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 66: | Line 66: | ||
| series = Annals of Discrete Mathematics | | series = Annals of Discrete Mathematics | ||
| title = Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday | | title = Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday | ||
| url = | | url = https://renyi.hu/~p_erdos/1982-12.pdf | ||
| volume = 12 | | volume = 12 | ||
| year = 1982 | | year = 1982 | ||
| Line 144: | Line 144: | ||
==External links== | ==External links== | ||
*[ | *[https://www.theoremoftheday.org/CombinatorialTheory/Panarboreal/TotDPanarboreal.pdf The panarborial formula], "Theorem of the Day" concerning universal graphs for trees | ||
{{DEFAULTSORT:Universal Graph}} | {{DEFAULTSORT:Universal Graph}} | ||
[[Category:Graph families]] | [[Category:Graph families]] | ||
[[Category:Infinite graphs]] | [[Category:Infinite graphs]] | ||
Latest revision as of 03:13, 25 December 2025
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 Richard 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 Template:Mvar: that is, an infinite graph belonging to Template:Mvar that contains all finite graphs in Template:Mvar. For instance, the Henson graphs are universal in this sense for the Template:Mvar-clique-free graphs.
A universal graph for a family Template:Mvar of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in Template:Mvar; 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 Template:Mvar-vertex trees, with only Template:Mvar vertices and O(n log n)Script error: No such module "Check for unknown parameters". edges, and that this is optimal.[6] A construction based on the planar separator theorem can be used to show that Template:Mvar-vertex planar graphs have universal graphs with O(n3/2)Script error: No such module "Check for unknown parameters". edges, and that bounded-degree planar graphs have universal graphs with O(n log n)Script error: No such module "Check for unknown parameters". edges.[7][8][9] It is also possible to construct universal graphs for planar graphs that have n1+o(1)Script error: No such module "Check for unknown parameters". vertices.[10] Sumner's conjecture states that tournaments are universal for polytrees, in the sense that every tournament with 2n − 2Script error: No such module "Check for unknown parameters". vertices contains every polytree with Template:Mvar vertices as a subgraph.[11]
A family Template:Mvar of graphs has a universal graph of polynomial size, containing every Template:Mvar-vertex graph as an induced subgraph, if and only if it has an adjacency labelling scheme in which vertices may be labeled by O(log n)Script error: No such module "Check for unknown parameters".-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in Template:Mvar may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label.[12]
In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph.
The notion of universal graph has been adapted and used for solving mean payoff games.[13]
References
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1"..
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1".
Script error: No such module "Check for unknown parameters".
External links
- The panarborial formula, "Theorem of the Day" concerning universal graphs for trees