Count Frucht

The Frucht graph is one of two minimal cubic graphs that do not have nontrivial automorphisms . The count was first described by in 1939. ^[1]

Properties

Count Frucht

Count Frucht is a graph of Halin with a chromatic number of 3.
- Like all Halin's graphs, the Frucht graph is planar , 3 is vertex-connected, and the .
It is a k-connected edge graph .
Its independence number is 5.
chromatic index 3,
radius 3,
diameter 4,
girth 3.

The Frucht graph is Hamiltonian and can be constructed from the [−5, −2, −4,2,5, −2,2,5, −2, −5,4,2].

The Frucht graph is one of two minimal cubic graphs that have a single automorphism — identity ^[3] (thus, any vertex can be topologically distinguishable from the others). Such graphs are called asymmetric graphs.
- Frucht's theorem states that any group can be represented as a group of symmetries of a graph, ^[1] and a strengthening of this theorem, also Frucht, claims that any group can be represented as a symmetry group of a 3-regular graph ^[4]. The Frucht graph gives an example of such an implementation for trivial group .

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

↑ ¹ ² R. Frucht. Herstellung von Graphen mit vorgegebener abstrakter Gruppe. // Compositio Mathematica. - 1939. - T. 6 . - S. 239–250 . - ISSN 0010-437X . .
↑ Weisstein, Eric W. Frucht Graph (English) on Wolfram MathWorld .
Ien Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990
↑ R. Frucht. Graphs of degree three with a given abstract group // Canadian Journal of Mathematics . - 1949.- T. 1 . - S. 365–378 . - ISSN 0008-414X . - DOI : 10.4153 / CJM-1949-033-6 . .