𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Exotic n-universal graphs

✍ Scribed by T. D. Parsons; Tomaž Pisanski

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
179 KB
Volume
12
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 sense of W.T Tutte and are of diameter ' 2 The automorphism group of G is a transitive rank 3 permutation group, I e , it acts transitively on (1) the vertices of G, (2) the ordered pairs uv of adjacent vertices of G, and (3) the ordered pairs x y of nonadjacent vertices of G

📜 SIMILAR VOLUMES

Universal graphs and induced-universal g
Universal graphs and induced-universal graphs
✍ Fan R. K. Chung 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB

## 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

Non-Ramsey Graphs Are c log n-
Non-Ramsey Graphs Are c log n-Universal
✍ Hans Jürgen Prömel; Vojtěch Rödl 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 98 KB

We prove that for any c 1 >0 there exists c 2 >0 such that the following statement is true: If G is a graph with n vertices and with the property that neither G nor its complement contains a complete graph K l , where l=c 1 log n then G is c 2 log n-universal, i.e., G contains all subgraphs with c 2

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