View source for Frucht theorem

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f1102101.png" /> there is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f1102102.png" />-regular graph whose automorphism group is isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f1102103.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f1102104.png" />, there is a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f1102105.png" /> with automorphism group isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f1102106.png" /> and such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f1102107.png" /> has a prescribed vertex connectivity, a prescribed chromatic number, or is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f1102108.png" />-regular for a given integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f1102109.png" />, or has a spanning subgraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f11021010.png" /> homeomorphic to a given connected graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f11021011.png" />.

These investigations have led to the study of graphical regular representations of groups. A graphical regular representation of a given abstract group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f11021012.png" /> is a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f11021013.png" /> whose automorphism group acts regularly on its vertex set and is isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f11021014.png" />. 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,   "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110210/f11021015.png" />-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>