Universal graph

Quality 0.50 · 3 views · Updated 2 months ago

title: "Universal graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-families", "infinite-graphs"] topic_path: "general/graph-families" source: "https://en.wikipedia.org/wiki/Universal_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

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{{cite journal | last1 = Rado | first1=R. | authorlink1=Richard Rado | title = Universal graphs and universal functions | journal = Acta Arithmetica | volume = 9 | issue = 4 | year = 1964 | pages = 331–340 | mr = 0172268 | doi=10.4064/aa-9-4-331-340| doi-access = free | last1 = Rado | first1=R. | authorlink1=Richard Rado | title = Universal graphs | date = 1967 | book-title = A Seminar in Graph Theory | publisher = Holt, Rinehart, and Winston | pages = 83–85 | mr = 0214507}} and is now called the Rado graph or random graph. More recent work{{cite journal |author1=Goldstern, Martin |author2=Kojman, Menachem | title = Universal arrow-free graphs | year = 1996 | journal = Acta Mathematica Hungarica | volume = 1973 | pages = 319–326 | doi = 10.1007/BF00052907 | doi-access = free | arxiv = math.LO/9409206 | mr = 1428038 | issue = 4}} | last1=Cherlin | first1=Greg | last2=Shelah | first2=Saharon | authorlink2=Saharon Shelah | last3=Shi | first3=Niandong | title = Universal graphs with forbidden subgraphs and algebraic closure | journal = Advances in Applied Mathematics | volume = 22 | year = 1999 | pages = 454–491 | doi = 10.1006/aama.1998.0641 | arxiv = math.LO/9809202 | mr = 1683298 | issue = 4|s2cid=17529604 }} 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. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.

::figure[src="https://upload.wikimedia.org/wikipedia/commons/4/49/Infinite_path.svg" caption="An infinite path is a universal graph for the family of path graphs."] ::

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 | author = Wu, A. Y. | title = Embedding of tree networks into hypercubes | journal = Journal of Parallel and Distributed Computing | volume = 2 | year = 1985 | pages = 238–249 | doi = 10.1016/0743-7315(85)90026-7 | issue = 3 }} 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-vertex trees, with only n vertices and O(n log n) edges, and that this is optimal. 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.{{Cite book | last1 = Babai | first1 = L. | author1-link = László Babai | last2 = Chung | first2 = F. R. K. | author2-link = Fan Chung | last3 = Erdős | first3 = P. | author3-link = Paul Erdős | last4 = Graham | first4 = R. L. | author4-link = Ronald Graham | last5 = Spencer | first5 = J. H. | author5-link = Joel Spencer | contribution = On graphs which contain all sparse graphs | editor1-last = Rosa | editor1-first = Alexander | editor2-last = Sabidussi | editor2-first = Gert | editor3-last = Turgeon | editor3-first = Jean | pages = 21–26 | 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 | url = https://renyi.hu/~p_erdos/1982-12.pdf | volume = 12 | year = 1982 | mr = 0806964}}{{Cite journal | last1 = Bhatt | first1 = Sandeep N. | last2 = Chung | first2 = Fan R. K. | author2-link = Fan Chung | last3 = Leighton | first3 = F. T. | author3-link = F. Thomson Leighton | last4 = Rosenberg | first4 = Arnold L. | author4-link = Arnold L. Rosenberg | doi = 10.1137/0402014 | journal = SIAM Journal on Discrete Mathematics | pages = 145–155 | title = Universal graphs for bounded-degree trees and planar graphs | volume = 2 | year = 1989 | issue = 2 | mr = 0990447}}{{Cite book | last = Chung | first = Fan R. K. | author-link = Fan Chung | contribution = Separator theorems and their applications | editor1-last = Korte | editor1-first = Bernhard | editor1-link = Bernhard Korte | editor2-last = Lovász | editor2-first = László | editor2-link = László Lovász | editor3-last = Prömel | editor3-first = Hans Jürgen | editor4-last = Schrijver | editor4-first = Alexander | display-editors = 3 | isbn = 978-0-387-52685-0 | pages = 17–34 | publisher = Springer-Verlag | series = Algorithms and Combinatorics | title = Paths, Flows, and VLSI-Layout | volume = 9 | year = 1990 | mr = 1083375 | url = https://archive.org/details/pathsflowsvlsila0000unse/page/17 | last1 = Dujmović | first1 = Vida | last2 = Esperet | first2 = Louis | last3 = Joret | first3 = Gwenaël | last4 = Gavoille | first4 = Cyril | last5 = Micek | first5 = Piotr | last6 = Morin | first6 = Pat | arxiv = 2003.04280 | title = Adjacency Labelling for Planar Graphs (And Beyond) | journal = Journal of the ACM | year = 2021| volume = 68 | issue = 6 | pages = 1–33 | doi = 10.1145/3477542 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.

A family F of graphs has a universal graph of polynomial size, containing every n-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)-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 F 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.{{citation | last1 = Kannan | first1 = Sampath | last2 = Naor | first2 = Moni | author2-link = Moni Naor | last3 = Rudich | first3 = Steven | author3-link = Steven Rudich | doi = 10.1137/0405049 | issue = 4 | journal = SIAM Journal on Discrete Mathematics | mr = 1186827 | pages = 596–603 | title = Implicit representation of graphs | volume = 5 | year = 1992}}.

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.

References

(1983). "On universal graphs for spanning trees". Journal of the London Mathematical Society.
[http://www.math.uiuc.edu/~west/openp/univtourn.html Sumner's Universal Tournament Conjecture], Douglas B. West, retrieved 2010-09-17.
(2018-07-27). "Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::