Universal graph

Universal graph

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 [cite journal
author = Rado, R.
title = Universal graphs and universal functions
journal = Acta Arithmetica
volume = 9
year = 1964
pages = 331–340] [cite conference
author = Rado, R.
title = Universal graphs
date = 1967
booktitle = A Seminar in Graph Theory
publisher = Holt, Reinhart, and Winston
pages = 83–85] and is now called the Rado graph or random graph. More recent work [cite journal
author = Goldstern, Martin; Kojman, Menachem
title = Universal arrow-free graphs
year = 1996
journal = Acta Math. Hungar.
volume = 1973
pages = 319–326
id = arxiv|archive = math.LO|id = 9409206
doi = 10.1007/BF00052907] [cite journal
author = Cherlin, Greg; Shelah, Saharon; Shi, Niandong
title = Universal graphs with forbidden subgraphs and algebraic closure
journal = Advances in Applied Math
volume = 22
year = 1999
pages = 454–491
id = arxiv|archive = math.LO|id = 9809202
doi = 10.1006/aama.1998.0641] 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 [cite journal
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] so a hypercube can be said to be a universal graph for trees.

In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Universal Networking Language — (UNL) is a declarative formal language specifically designed to represent semantic data extracted from natural language texts. It can be used as a pivot language in interlingual machine translation systems or as a knowledge representation… …   Wikipedia

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Graph of groups — In geometric group theory, a graph of groups is an object consisting of a collection of groups indexed by the vertices and edges of a graph, together with a family of injective homomorphisms of the edge groups into the vertex groups.There is a… …   Wikipedia

  • Rado graph — The Rado graph, as numbered by Rado (1964). 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 (up to isomorphism) countable graph R such that for any finite graph G… …   Wikipedia

  • Covering graph — 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 the vertex set of G. A covering map f is a surjection and a local isomorphism: the… …   Wikipedia

  • Coordinated Universal Time — UTC redirects here. For other uses, see UTC (disambiguation). Coordinated Universal Time (abbreviated UTC) is the primary time standard by which the world regulates clocks and time. It is one of several closely related successors to Greenwich… …   Wikipedia

  • Quantum graph — In mathematics and physics, a quantum graph is a linear, network shaped structure whose time evolution is described by a system of schrödinger equations or, more generally, by a set of evolution equations associated with differential or pseudo… …   Wikipedia

  • Conceptual graph — Conceptual graphs (CGs) are a formalism for knowledge representation. In the first published paper on CGs, John F. Sowa (Sowa 1976) used them to represent the conceptual schemas used in database systems. The first book on CGs (Sowa 1984) applied… …   Wikipedia

  • Primal constraint graph — In constraint satisfaction, the primal constraint graph or simply primal graph (also the Gaifman graph) of a constraint satisfaction problem is the graph whose nodes are the variables of the problem and an edge joins a pair of variables if the… …   Wikipedia

  • Grafo universal — En teoría de grafos, un grafo universal es un grafo infinito que contiene a todos los grafos finitos (o al menos numerables) como un subgrafo inducido. El primer grafo universal fue construido por R. Rado,[1] [2] actualmente llamado grafo de Rado …   Wikipedia Español

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”