Frucht graph

Frucht graph
The Frucht graph
Named after	Robert Frucht
Vertices	12
Edges	18
Radius	3
Diameter	4
Girth	3
Automorphisms	1 ({id})
Chromatic number	3
Chromatic index	3
Properties	Cubic Halin Pancyclic
Table of graphs and parameters

In the mathematical field of graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries. ^[1] It was first described by Robert Frucht in 1949. ^[2]

The Frucht graph can be constructed from the LCF notation: [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2].

Properties

The Frucht graph is one of the five smallest cubic graphs possessing only a single graph automorphism, the identity: every vertex can be distinguished topologically from every other vertex. ^[3] Such graphs are called asymmetric (or identity) graphs. Frucht's theorem states that any finite group can be realized as the group of symmetries of a graph, ^[4] and a strengthening of this theorem, also due to Frucht, states that any finite group can be realized as the symmetries of a 3-regular graph. ^[2] The Frucht graph provides an example of this strengthened realization for the trivial group.

The characteristic polynomial of the Frucht graph is ${\displaystyle (x-3)(x-2)x(x+1)(x+2)(x^{3}+x^{2}-2x-1)(x^{4}+x^{3}-6x^{2}-5x+4)}$.

The Frucht graph is a pancyclic, Halin graph with chromatic number 3, chromatic index 3, radius 3, and diameter 4. Like every Halin graph, the Frucht graph is polyhedral (planar and 3-vertex-connected) ^[5] and Hamiltonian, with girth 3. Its independence number is 5.

Gallery

• 
  The chromatic number of the Frucht graph is 3.
• 
  The Frucht graph is Hamiltonian.

References

1. Weisstein, Eric W., "Frucht Graph", MathWorld
2. Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics , 1 (4): 365–378, doi: 10.4153/CJM-1949-033-6 , ISSN   0008-414X, MR   0032987, S2CID   124723321
3. Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M.; Seidel, J. J. (1976), Computer investigation of cubic graphs, EUT report, vol. 76-WSK-01, Department of Mathematics and Computing Science, Eindhoven University of Technology
4. Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica (in German), 6: 239–250, ISSN   0010-437X, Zbl   0020.07804
5. Lokesha, V. (2015), "Harmonic Index of Cubic Polyhedral Graphs Using Bridge Graphs" (PDF), Hikari: Applied Mathematical Sciences, 9 (85): 4245–4253, doi:10.12988/ams.2015.53280