Namespaces
Variants
Actions

Difference between revisions of "Frucht theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
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" />.
+
{{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]]].
 
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" />.
+
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 <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]]].
+
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====
 
====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>
+
<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>

Revision as of 14:21, 1 May 2014

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
How to Cite This Entry:
Frucht theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Frucht_theorem&oldid=32027
This article was adapted from an original article by K.R. Parthasarathy (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article