Folkman graph
| Folkman graph | |
|---|---|
Drawing following Folkman (1967), Figure 1 | |
| Named after | Jon Folkman |
| Vertices | 20 |
| Edges | 40 |
| Radius | 3 |
| Diameter | 4 |
| Girth | 4 |
| Automorphisms | 5! ยท 25 = 3840 |
| Chromatic number | 2 |
| Chromatic index | 4 |
| Genus | 3 |
| Book thickness | 3 |
| Queue number | 2 |
| Properties | |
| Table of graphs and parameters | |
In the mathematical field of graph theory, the Folkman graph is a graph with 20 vertices and 40 edges. It is quartic (four edges meet at each vertex), and bipartite (its vertices can be divided into two subsets with each edge crossing from one subset to the other). It has symmetries taking every edge to every other edge, but not taking every vertex to every other vertex, making it the smallest possible semi-symmetric graph. It is named after Jon Folkman, who constructed it for this property in 1967.
The Folkman graph can be constructed either using modular arithmetic or as the subdivided double of the five-vertex complete graph. Beyond the investigation of its symmetry, it has also been used to construct isospectral graphs and investigated as a counterexample for certain questions of graph embedding.