Frucht graph

Last updated

Frucht graph
Frucht planar Lombardi.svg
The Frucht graph
Named afterRobert Frucht
Vertices 12
Edges 18
Radius 3
Diameter 4
Girth 3
Automorphisms identity
Chromatic number 3
Chromatic index 3
Properties Cubic
Halin
Pancyclic
Table of graphs and parameters

In 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]

Contents

The Frucht graph can be constructed from the LCF notation: [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2]. This describes it as a cubic graph in which two of the three adjacencies of each vertex form part of a Hamiltonian cycle and the numbers specify how far along the cycle to find the third neighbor of each vertex. [3]

Properties

The Frucht graph is a cubic graph, because three vertices are incident to every vertex, thereby the degree of every vertex is 3. It 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. [4] 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, [5] 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.

Frucht graph as a convex polyhedron Frucht graph as a convex polyhedron.svg
Frucht graph as a convex polyhedron

The Frucht graph is a Halin graph, a type of planar graph formed from a tree with no degree-two vertices by adding a cycle connecting its leaves. [1] Every Halin graph is 3-vertex-connected: deleting two of its vertices cannot disconnect it. By Steinitz's theorem, the Frucht graph is hence polyhedral, meaning its 12 vertices and 18 edges form the skeleton of a convex polyhedron. [6] It is also Hamiltonian.

It is pancyclic, [7] with chromatic number 3, chromatic index 3, radius 3, and diameter 4. Its girth 3. Its independence number is 5.

The characteristic polynomial of the Frucht graph is .

References

  1. 1 2 Ali, Akbar; Chartrand, Gary; Zhang, Ping (2021), Irregularity in Graphs, Springer, pp. 24–25, doi:10.1007/978-3-030-67993-4, ISBN   978-3-030-67993-4
  2. 1 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. ↑ Weisstein, Eric W., "Frucht Graph", MathWorld {{cite web}}: CS1 maint: overridden setting (link)
  4. ↑ 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
  5. ↑ Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica (in German), 6: 239–250, ISSN   0010-437X, Zbl   0020.07804
  6. ↑ Weisstein, Eric W., "Halin Graph", MathWorld
  7. ↑ Parrochia, Daniel (2023), Mathematics and Philosophy 2: Graphs, Orders, Infinites and Philosophy, John & Wiley, ISTE Ltd., p. 18

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.