Namespaces
Variants
Actions

Difference between revisions of "Frucht theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
m (link)
 
Line 1: Line 1:
 
{{TEX|done}}
 
{{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$.
+
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]]].

Latest revision as of 09:29, 19 January 2021

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