Graphs with given automorphism group and few edge orbits (Q1176027)

A simple graph \(X\) is said to ``represent the group \(G\) with \(k\) edge- orbits and \(m\) vertex-orbits'' if \(\hbox{Aut}(X)\cong G\) (abstractly) and \(G\) acts with \(k\) orbits on \(E(X)\) and \(m\) orbits on \(V(X)\). L. Babai showed (1974) that (with three exceptions) every finite group can be represented with \(\leq 2\) vertex-orbits but conjectured (1981, proved by A. J. Goodman (submitted) in 1990) that for any \(k\) there exists \(G\) such that any graph representing \(G\) has at least \(k\) edge orbits. Nonetheless, it is shown that many large classes of finite and infinite groups admit representations with a bounded number of edge-orbits. This lucidly written paper concludes with six open problems and conjectures.