View source for Frucht theorem

{{TEX|done}}
In 1938, R. Frucht [[#References|[a1]]] affirmatively answered a question posed by D. König [[#References|[a2]]], by proving that every abstract [[Group|group]] is isomorphic to the [[Automorphism|automorphism]] group of some [[Graph|graph]] (cf. also [[Graph automorphism|Graph automorphism]]). This is know as Frucht's theorem. In 1949, Frucht [[#References|[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 [[#References|[a4]]]. For an alternative proof of Frucht's theorem see [[#References|[a5]]].

G. Sabidussi [[#References|[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 [[#References|[a7]]].

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