Frucht theorem

In 1938, R. Frucht [a1] affirmatively answered a question posed by D. König [a2], by proving that every abstract group is isomorphic to the automorphism group of some graph (cf. also Graph automorphism). This is know as Frucht's theorem. In 1949, Frucht [a3] extended this result by showing that for every abstract group $\Gamma$ there is a $3$-regular graph whose automorphism group is isomorphic to $\Gamma$.

For a proof of these results see [a4]. For an alternative proof of Frucht's theorem see [a5].

G. Sabidussi [a6] further extended this result by proving that, given an abstract group $\Gamma$, there is a graph $G$ with automorphism group isomorphic to $\Gamma$ and such that $G$ has a prescribed vertex connectivity, a prescribed chromatic number, or is $k$-regular for a given integer $k$, or has a spanning subgraph $\widetilde H$ homeomorphic to a given connected graph $H$.

These investigations have led to the study of graphical regular representations of groups. A graphical regular representation of a given abstract group $\Gamma$ is a graph $G$ whose automorphism group acts regularly on its vertex set and is isomorphic to $\Gamma$. A sample reference is [a7].

References

[a1]	R. Frucht, "Hertellung von Graphen mit vorgegebenen Abstrakten Gruppen" Compositio Math. , 6 (1938) pp. 239–250
[a2]	D. König, "Theorie der Endlichen und Unendlichen Graphen" , Leipzig (1936)
[a3]	R. Frucht, "Graphs of degree three with a given abstract group" Canad. J. Math. , 1 (1949) pp. 365–378
[a4]	L. Lovász, "Combinatorial problems and exercises" , North-Holland (1979)
[a5]	V. Krishnamoorthy, K.R. Parthasarathy, "$F$-sets in graphs" J. Combin. Th. B , 24 (1978) pp. 53–60
[a6]	G. Sabidussi, "Graphs with given groups and given graph-theoretical properties" Canad. J. Math. , 9 (1957) pp. 515–525
[a7]	M.E. Watkins, "On the action of non-abelian groups on graphs" J. Combin. Th. , 11 (1971) pp. 95–104