𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Universal graphs and induced-universal graphs

✍ Scribed by Fan R. K. Chung

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
484 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We construct graphs that contain all bounded‐degree trees on n vertices as induced subgraphs and have only cn edges for some constant c depending only on the maximum degree. In general, we consider the problem of determining the graphs, so‐called universal graphs (or induced‐universal graphs), with as few vertices and edges as possible having the property that all graphs in a specified family are contained as subgraphs (or induced subgraphs). We obtain bounds for the size of universal and induced‐universal graphs for many classes of graphs such as trees and planar graphs. These bounds are obtained by establishing relationships between the universal graphs and the induced‐universal graphs.

📜 SIMILAR VOLUMES

Exotic n-universal graphs
Exotic n-universal graphs
✍ T. D. Parsons; Tomaž Pisanski 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 179 KB

An n-universal graph is a graph that contains as an induced subgraph a copy of every graph on n vertices It is shown that for each positive integer n > 1 there exists an n-universal graph G on 4" -1 vertices such that G IS a (v, k, A)-graph, and both G and its complement G are l-transitive in the se

On the existence of countable universal
On the existence of countable universal graphs
✍ F�redi, Zolt�n; Komj�th, P�ter 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB 👁 2 views

Let Forb(G) denote the class of graphs with countable vertex sets which do not contain G as a subgraph. If G is finite, 2-connected, but not complete, then Forb(G) has no element which contains every other element of Forb(G) as a subgraph, i.e., this class contains no universal graph.

Density of universal classes of series-p
Density of universal classes of series-parallel graphs
✍ Jaroslav Nešetřil; Yared Nigussie 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 1 views

## Abstract A class of graphs ${\cal C}$ ordered by the homomorphism relation is __universal__ if every countable partial order can be embedded in ${\cal C}$. It is known (see [1,3]) that the class $\cal C\_{k}$ of __k__‐colorable graphs, for any fixed ${k}\geq 3 $, induces a universal partial orde

Universality of A-mote Graphs
Universality of A-mote Graphs
✍ Roland Häggkvist; Pavol Hell 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 160 KB