The Count Folkman (named after John Folkman) is a bipartite 4- regular graph with 20 vertices and 40 edges [1] .
| Count Folkman | |
|---|---|
 Count Folkman | |
| Named after | J. Folkman |
| Tops | 20 |
| Rib | 40 |
| Radius | 3 |
| Diameter | four |
| Girth | four |
| Automorphisms | 3840 |
| Chromatic number | 2 |
| Chromatic Index | four |
| Properties | Dicotyledonous Hamiltonian Semi-symmetrical Regular Euler Perfect |
Folkman's graph is Hamiltonian and has chromatic number 2, chromatic index 4, radius 3, diameter 4 and girth 4. It is also vertex 4-connected , edge 4-connected and perfect . The graph has a book investment of 3 and the number of queues 2 [2] .
Content
Algebraic properties
The automorphism group of the Folkman graph acts transitively on its edges, but not on its vertices. This is the smallest undirected graph that is edge-transitive and regular, but not vertex-transitive [3] . Such graphs are called semi-symmetric , they were first studied by Folkman in 1967 and discovered a graph with 20 vertices, which was later named after him [4] .
As a semi-symmetric graph, the Folkman graph is bipartite and its automorphism group acts transitively on every fraction of the vertices of a bipartite graph. In the diagram below, showing the chromatic number of the graph, green vertices cannot be reflected in red by any automorphism, but any red vertex can be reflected in any other red vertex, and any green vertex - in any other green vertex.
The characteristic polynomial of the Folkman graph is .
Gallery
The chromatic index of the Folkman graph is 4.
The chromatic number of the Folkman graph is 2.
Count Folkman is Hamiltonian .
Notes
- ↑ Weisstein, Eric W. Folkman graph (English) on the Wolfram MathWorld website.
- ↑ Wolz, 2018 .
- ↑ Skiena, 1990 , p. 186-187.
- ↑ Folkman, 1967 , p. 215-232.
Literature
- Skiena S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading. - MA: Addison-Wesley, 1990.
- Jessica Wolz. Engineering Linear Layouts with SAT. - University of Tübingen, 2018. - (Master Thesis).
- Folkman J. Regular line-symmetric graphs // Journal of Combinatorial Theory. - 1967. - V. 3 , no. 3 - DOI : 10.1016 / S0021-9800 (67) 80069-3 .