ⓘ Universal graph. In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type ..


ⓘ Universal graph

In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by Richard 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. For instance, the Henson graphs are universal in this sense for the i -clique-free graphs.

A universal graph for a family 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 -vertex trees, with only n vertices and On 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 On 3/2 edges, and that bounded-degree planar graphs have universal graphs with On log n edges. It is also possible to construct universal graphs for planar graphs that have On 4/3 vertices. Sumners conjecture states that tournaments are universal for polytrees, in the sense that every tournament with 2 n − 2 vertices contains every polytree with n vertices as a subgraph.

A family 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.

The notion of universal graph has been adapted and used for solving mean payoff games.

  • 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
  • In the mathematical field of graph theory, the Rado graph Erdos Renyi graph or random graph is a countably infinite graph that can be constructed with
  • 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
  • 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 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
  • In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only
  • This is a glossary of graph theory terms. Graph theory is the study of graphs systems of nodes or vertices connected in pairs by edges. Contents:
  • logic of graphs 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
  • specifically in graph theory, a vertex plural vertices or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set
  • 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
  • chordal graphs, and the graphs that contain a universal vertex. Cop - win graphs and the complementary class of graphs robber - win graphs were introduced by
  • 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
  • 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