Homage to roberto frucht

In the first book on graph theory ever written, Ddnes Konig [8, p. 51 defined the (abstract) group of a given graph and asked in 1936, “Wann kann eine gegebene abstrakte Gruppe als die Gruppe eines Graphen aufgefasst werden und-ist dies der Fall-wie kann dann der entsprechende Graph konstruiert werden?” Almost immediately, Roberto Frucht 141 answered this question in 1938 in the aflliative, when he gwvc a constrxtive proof that for any given finite abstract group A , there exists a graph G whose automorphism (permutation) group r(G) is isomorphic to A . Both :his theorem and his demonstration using the Cayley graph of the group have become classic and constitute the cornerstone of the interaction between graphs and groups. All graph theorists acknowledge this as an important pioneering result. Many subsequent papers including some by Frucht himself have weakened the hypothesis by proving that many varied properties of a graph G with r( G) isomorphic to the given abstract group A can be specified. Surely the most far-reaching such discovery is due to Babai [2], who used a categorytheoretic approach. A very special case of his most general result shows that for any two abstract groups A and B, there exists a graph G having an edge e such that r( G ) Another direction in which Frucht’s theorem has stimulated important results involves the determination, given A , of the number a(A) that is the smallest number of points in a graph G such that r(G) A . The most recent and definitive result is that of Arlinghaus [l], who derived a(A) for any Abelian group A! He also summarized all the known results obtaining a(A) for other groups A . The related invariant p(A), the minimum number of points in a digraph D such that r (D) Y A , has not been much studied. It is not even known for whichA is p(A) = a@). A third very important research direction stemming from Frucht’s original work involves the application of graphs and groups to the embedding of graphs in surfaces, and has even produced the concept of the genus of a group. The definitive work on this subject is the monograph by White A and r( G e) z B!