Frucht graph
Template:Short description Template:CS1 config
Page Template:Infobox graph/styles.css has no content.Page Module:Infobox/styles.css has no content.
| Frucht graph | |
|---|---|
| Lua error in package.lua at line 80: module 'Module:InfoboxImage/data' not found. The Frucht graph | |
| Named after | Robert 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]
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.
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 .
Gallery
-
The chromatic number of the Frucht graph is 3.
-
The Frucht graph is Hamiltonian.
References
Page Module:Side box/styles.css has no content.Page Template:Sister project/styles.css has no content.
Page Template:Reflist/styles.css has no content.
- ^ a b Page Module:Citation/CS1/styles.css has no content.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
- ^ a b Page Module:Citation/CS1/styles.css has no content.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
- ^ Script error: No such module "Template wrapper".
- ^ Page Module:Citation/CS1/styles.css has no content.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
- ^ Page Module:Citation/CS1/styles.css has no content.Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804
{{citation}}: CS1 maint: unrecognized language (link) - ^ Script error: No such module "Template wrapper".
- ^ Page Module:Citation/CS1/styles.css has no content.Parrochia, Daniel (2023), Mathematics and Philosophy 2: Graphs, Orders, Infinites and Philosophy, John & Wiley, ISTE Ltd., p. 18, ISBN 978-1-78630-897-9
Further reading
- Page Module:Citation/CS1/styles.css has no content.Sudev, N. K.; Germina, K. A. (2014), "A Note on the Sparing Number of Graphs", Advances and Applications in Discrete Mathematics, 14 (1): 51–65, arXiv:1402.4871
- Page Module:Citation/CS1/styles.css has no content.Fullarton, Neil J. (2016), "On the number of outer automorphisms of the automorphism group of a right-angled Artin group", Mathematical Research Letters, 23 (1): 145–162, arXiv:1306.6549, doi:10.4310/MRL.2016.v23.n1.a8, MR 3512881
