Universal graph
Encyclopedia
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 and is now called the Rado graph
or random graph. More recent work
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
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-node 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 graph
s have universal graphs with O(n3/2) edges, and that bounded-degree planar graphs have universal graphs with O(n log n) edges. Sumner's conjecture states that tournaments
are universal for polytree
s, 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.
In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a universal graph is an infinite graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
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 and is now called the Rado graph
Rado graph
In the mathematical field of graph theory, the Rado graph, also known as the random graph or the Erdős–Renyi graph, is the unique countable graph R such that for any finite graph G and any vertex v of G, any embedding of G − v as an induced subgraph of R can be extended to an...
or random graph. More recent work
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
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-node trees with only n vertices and O(n log n) edges, and that this is optimal. A construction based on the planar separator theorem
Planar separator theorem
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...
can be used to show that n-vertex planar graph
Planar graph
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 only at their endpoints...
s have universal graphs with O(n3/2) edges, and that bounded-degree planar graphs have universal graphs with O(n log n) edges. Sumner's conjecture states that tournaments
Tournament (graph theory)
A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph. That is, it is a directed graph in which every pair of vertices is connected by a single directed edge....
are universal for polytree
Polytree
In graph theory, a polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph for which there are no undirected cycles either...
s, 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
Implicit graph
In the study of graph algorithms, an implicit graph representation is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some more concise input.-Neighborhood representations:The notion of an implicit graph...
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.
In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
.