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 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.
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-vertex 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] It is also possible to construct universal graphs for planar graphs that have n1+o(1) vertices.[10]
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.[11]
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.[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]
^Rado, R. (1964). "Universal graphs and universal functions". Acta Arithmetica. 9 (4): 331–340. doi:10.4064/aa-9-4-331-340. MR 0172268.
^Rado, R. (1967). "Universal graphs". A Seminar in Graph Theory. Holt, Rinehart, and Winston. pp. 83–85. MR 0214507.
^Cherlin, Greg; Shelah, Saharon; Shi, Niandong (1999). "Universal graphs with forbidden subgraphs and algebraic closure". Advances in Applied Mathematics. 22 (4): 454–491. arXiv:math.LO/9809202. doi:10.1006/aama.1998.0641. MR 1683298. S2CID 17529604.
^
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.
^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. CiteSeerX 10.1.1.108.3415. doi:10.1112/jlms/s2-27.2.203. MR 0692525..
^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. MR 0806964.
^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–155. doi:10.1137/0402014. MR 0990447.
^Chung, Fan R. K. (1990). "Separator theorems and their applications". In Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; et al. (eds.). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics. Vol. 9. Springer-Verlag. pp. 17–34. ISBN 978-0-387-52685-0. MR 1083375.
^Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2021), "Adjacency Labelling for Planar Graphs (And Beyond)", Journal of the ACM, 68 (6): 1–33, arXiv:2003.04280, doi:10.1145/3477542
^Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
^Kannan, Sampath; Naor, Moni; Rudich, Steven (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics, 5 (4): 596–603, doi:10.1137/0405049, MR 1186827.
^Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (2018-07-27). "Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games". Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2333–2349. arXiv:1807.10546. doi:10.1137/1.9781611975482.142. ISBN 978-1-61197-548-2. S2CID 51865783.
mathematics, a universalgraph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universalgraph of this...
A graph database (GDB) is a database that uses graph structures for semantic queries with nodes, edges, and properties to represent and store data. A key...
Appendix:Glossary of graph theory in Wiktionary, the free dictionary. This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes...
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect...
computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals...
In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with...
discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices...
In the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a graph whose vertices or edges are not represented...
friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex, which becomes a universal vertex for the graph. By construction...
In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to...
mathematics, especially in the fields of universal algebra and graph theory, a graph algebra is a way of giving a directed graph an algebraic structure. It was...
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split...
In the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of...
useful universal function approximation on graphs (or rather on graph isomorphism classes) has been a longstanding problem. The popular graph convolutional...
first of these graphs, G3, is also called the homogeneous triangle-free graph or the universal triangle-free graph. To construct these graphs, Henson orders...
In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating...
Coordinated Universal Time (UTC) is the primary time standard globally used to regulate clocks and time. It establishes a reference for the current time...
In graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they...
decidable? The universality problem for C-free graphs: For which finite sets C of graphs does the class of C-free countable graphs have a universal member under...
A conceptual graph (CG) is a formalism for knowledge representation. In the first published paper on CGs, John F. Sowa (Sowa 1976) used them to represent...
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every...
In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a...
copies of the complete graph Kk at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs. It has n(k – 1) + 1 vertices and nk(k...
from expanding too rapidly and becoming too large to fit within a small graph. The markings on slide rules are arranged in a log scale for multiplying...
ISBN 978-0-521-63550-9. Truss, J. K. (September 1985). "The group of the countable universalgraph". Mathematical Proceedings of the Cambridge Philosophical Society....
from the universal set. Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding...
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract...
covering map of Cayley graphs φ* : Γ(F) → Γ(G), in fact a universal covering. Hence, the fundamental group of the Cayley graph Γ(G) is isomorphic to the...
Global Information