In Automorphisms of graphs, Peter J. Cameron mentioned following classes of graphs which are universal structures.
- graphs of valency k for any fixed k > 2;
- bipartite graphs;
- strongly regular graphs;
- Hamiltonian graphs;
- k-connected graphs, for k > 0;
- k-chromatic graphs, for k > 1;
- switching classes of graphs;
- lattices;
- projective planes (possibly infinite);
- Steiner triple systems;
- symmetric designs (BIBDs).
Cameron mentioned that the results are due to people like Frucht, Sabidussi, Mendelsohn, Babai, Kantor, and others.
My question:
Could anyone please point me to the individual reference for all or some of the classes?
Chapter 27 of Babai's "Handbook of Combinatorics" discusses automorphism groups, and in particular section 4 covers the universality problem. He does provide a number of references. You can access the chapter here.
Trivalent graphs: R. Frucht, "Graphs of degree 3 with given abstract group", Canad. J. Math. 1 (1949), 365-378.
Regular graphs (valency $k \ge 4$), $k$-connected graphs, Hamiltonian graphs: G. Sabidussi, "Graphs with given automorphism group and given graph theoretical properties", Canad. J. Math. 9 (1957), 515–525. [ paper ]
Strongly regular graphs: E. Mendelsohn, "Every (finite) group is the group of automorphisms of a (finite) strongly regular graph", Ars. Combinatoria 6 (1978), 75–86.
Lattices: G. Birkhoff, "Sobre los grupos de automorfismos", Revista Uni´on Math. Argentina 11 (1945), 155–157. [ paper (in Spanish (I presume)) ]
Steiner triple systems: E. Mendelsohn, "On the groups of automorphisms of Steiner triple and quadruple systems", J. Comb. Theory A 25 (1978), 97–104. [ paper ]
Those were the references I extracted from that section. Babai does refer to a survey of his own for proofs and further references:
L. Babai, "On the abstract group of automorphisms", In Combinatorics, volume 52 of London Math. Soc. Lecture Notes, pages 1–40. Cambridge Univ. Press, London, 1981. [ preview ]