Exotic n ‐universal graphs

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 n ‐ 1 vertices such that G is a ( v, k , λ)‐graph, and both G and its complement G¯ are 1‐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 xy of nonadjacent vertices of G .