ABSTRACT

We survey results about graphs with a prescribed abstract group of automorphisms. A graph X is said to represent a group G if Aut * X ≅ G. A class c of graphs is (f)-universal if its (finite) members represent all (finite) groups. Universality results prove independence of the group structure of Aut X and of combinatorial properties of X whereas non-universality results establish links between them. We briefly survey universality results and techniques and discuss some nonuniversality results in detail. Further topics include the minimum order of graphs representing a given group (upper vs. lower bounds, the same dilemma), vertex transitive and regular representation, endomorphis monoids. Attention is given to certain particular classes of graphs (subcontraction closed classes, trivalent graphs, strongly regular graphs) as well as to other combinatorial structures (Steiner triple systems, lattices). Other areas related to graph automorphisms are briefly mentioned. Numerous unsolved problems and conjectures are proposed.

O. AUTOMORPHISM GROUPS – A BRIEF SURVEY

In two of his papers in I878, Cayley introduced what has since become familiar under the name “Cayley diagrams”: a graphic representation of groups. Combined with a symmetrical embedding of the diagram on a suitable surface, this representation has turned out to be a powerful tool in the search for generators and relators for several classes of finite and finitely generated groups. This approach is extensively used in the classic book of Coxeter and Moser [CM 57] where a very accurate account of early and more recent references is also given.