On minimal <i>n</i>-universal graphs

Abstract

A graph G n consists of n distinct vertices x 1 x 2 , …, x n some pairs of which are joined by an edge. We stipulate that at most one edge joins any two vertices and that no edge joins a vertex to itself. If x i , and x j are joined by an edge, we denote this by writing x i ∘ x j . Consider a second graph H N , where n ≦ N . Following Rado [1], we say that a one-to-one mapping/of the vertices of G n into the vertices of H N defines an embedding if x i ∘ x j implies f ( x i ) ∘ f ( x j ), and conversely, for all i, j = 1, 2,…, n . If there exists an embedding of G n into H N , we denote this by writing G n &lt; H N . The particular graph H N is said to be n-universal if G n &lt; H N for every graph G n with n vertices.

Locations

• Proceedings of the Glasgow Mathematical Association - View - PDF