Premium
Exotic n ‐universal graphs
Author(s) -
Parsons T. D.,
Pisanski Tomaž
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120204
Subject(s) - combinatorics , mathematics , path graph , discrete mathematics , vertex transitive graph , graph , complement graph , wheel graph , graph power , line graph
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 .