Universal graph

Last updated

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]

Related Research Articles

<span class="mw-page-title-main">Tree (graph theory)</span> Undirected, connected and acyclic graph

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Spanning tree</span> Tree which includes all vertices of a graph

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one. To distinguish these graphs from the larger family of their subgraphs, they may be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are subgraphs of unit distance graphs.

<span class="mw-page-title-main">Rado graph</span> Infinite graph containing all countable graphs

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 by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

<span class="mw-page-title-main">Median graph</span> Graph with a median for each three vertices

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c.

<span class="mw-page-title-main">Hypohamiltonian graph</span>

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

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 into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

<span class="mw-page-title-main">Halin graph</span> Mathematical tree with cycle through leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

<span class="mw-page-title-main">Sumner's conjecture</span>

Sumner's conjecture states that every orientation of every -vertex tree is a subgraph of every -vertex tournament. David Sumner, a graph theorist at the University of South Carolina, conjectured in 1971 that tournaments are universal graphs for polytrees. The conjecture was proven for all large by Daniela Kühn, Richard Mycroft, and Deryk Osthus.

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

<span class="mw-page-title-main">Graph power</span> Graph operation: linking all pairs of nodes of distance ≤ k

In graph theory, a branch of mathematics, the kth powerGk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc.

In graph theory and graph drawing, a subhamiltonian graph is a subgraph of a planar Hamiltonian graph.

<span class="mw-page-title-main">Queue number</span> Invariant in graph theory

In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.

<span class="mw-page-title-main">Distinguishing coloring</span> Assignment of colors to graph vertices that destroys all symmetries

In graph theory, a distinguishing coloring or distinguishing labeling of a graph is an assignment of colors or labels to the vertices of the graph that destroys all of the nontrivial symmetries of the graph. The coloring does not need to be a proper coloring: adjacent vertices are allowed to be given the same color. For the colored graph, there should not exist any one-to-one mapping of the vertices to themselves that preserves both adjacency and coloring. The minimum number of colors in a distinguishing coloring is called the distinguishing number of the graph.

<span class="mw-page-title-main">Universal vertex</span> Vertex adjacent to all others in a graph

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 vertex, as it forms a one-element dominating set in the graph.

References

  1. ↑ Rado, R. (1964). "Universal graphs and universal functions". Acta Arithmetica. 9 (4): 331–340. doi: 10.4064/aa-9-4-331-340 . MR   0172268.
  2. ↑ Rado, R. (1967). "Universal graphs". A Seminar in Graph Theory. Holt, Rinehart, and Winston. pp. 83–85. MR   0214507.
  3. ↑ Goldstern, Martin; Kojman, Menachem (1996). "Universal arrow-free graphs". Acta Mathematica Hungarica . 1973 (4): 319–326. arXiv: math.LO/9409206 . doi: 10.1007/BF00052907 . MR   1428038.
  4. ↑ 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.
  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. CiteSeerX   10.1.1.108.3415 . doi:10.1112/jlms/s2-27.2.203. MR   0692525..
  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. MR   0806964.
  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–155. doi:10.1137/0402014. MR   0990447.
  9. ↑ 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.
  10. ↑ 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
  11. ↑ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
  12. ↑ 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 .
  13. ↑ 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.