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
Book thickness	3
Queue number	2
Properties	Bipartite Eulerian Hamiltonian Regular Semi-symmetric
Table of graphs and parameters

In the mathematical field of graph theory, the Folkman graph is a 4-regular graph with 20 vertices and 40 edges. It is a bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not symmetric with each other, making it the smallest possible semi-symmetric graph. It is named after Jon Folkman, who constructed it for this property in 1967.

Construction

Construction of the Folkman graph from the complete graph $K_{5}$. The green vertices subdivide each edge of $K_{5}$, and the red pairs of vertices are the result of doubling the five vertices of $K_{5}$.

Folkman's original construction of this graph was the simplest case of a more general construction of semi-symmetric graphs using modular arithmetic, based on a prime number $p$ congruent to 1 mod 4. For each such prime, there is a number $r$ such that $r^{2}=-1$ mod $p$, and Folkman uses modular arithmetic to construct a semi-symmetric graph with $2pr$ vertices. The Folkman graph is the result of this construction for $p=5$ and $r=2$.

Another construction for the Folkman graph begins with the complete graph on five vertices, $K_{5}$. A new vertex is placed on each of the ten edges of $K_{5}$, subdividing each edge into a two-edge path. Then, each of the five original vertices of $K_{5}$ is doubled, replacing it by two vertices with the same neighbors. The ten subdivision vertices form one side of the bipartition of the Folkman graph, and the ten vertices in twin pairs coming from the doubled vertices of $K_{5}$ form the other side of the bipartition.

Because each edge of the result comes from a doubled half of an edge of $K_{5}$, and because $K_{5}$ has symmetries taking every half-edge to every other half-edge, the result is edge-transitive. It is not vertex-transitive, because the subdivision vertices are not twins with any other vertex, making them different from the doubled vertices coming from $K_{5}$.

Algebraic properties

The automorphism group of the Folkman graph (its group of symmetries) combines the $5!$ symmetries of $K_{5}$ with the $2^{5}$ ways of swapping some pairs of doubled vertices, for a total of $5!\cdot 2^{5}=3840$ symmetries. This group acts transitively on the Folkman graph's edges (it includes a symmetry taking any edge to any other edge) but not on its vertices. The Folkman graph is the smallest undirected graph that is edge-transitive and regular, but not vertex-transitive. Such graphs are called semi-symmetric graphs and were first studied by Folkman in 1967 who discovered the graph on 20 vertices that now is named after him.

Like all semi-symmetric graphs, the Folkman graph is bipartite. Its automorphism group includes symmetries taking any vertex to any other vertex that is on the same side of the bipartition, but none that take a vertex to the other side of the bipartition. Although one can argue directly that the Folkman graph is not vertex-transitive, this can also be explained group-theoretically: its symmetries act primitively on the vertices constructed as subdivision points of $K_{5}$, but imprimitively on the vertices constructed by doubling the vertices of $K_{5}$. Every symmetry maps a doubled pair of vertices to another doubled pair of vertices, but there is no grouping of the subdivision vertices that is preserved by the symmetries.

The characteristic polynomial of the Folkman graph is $(x-4)x^{10}(x+4)(x^{2}-6)^{4}$.

Other properties

The Folkman graph with its vertices arranged in a Hamiltonian cycle. The edges that are not used in this cycle form the second Hamiltonian cycle of a Hamiltonian decomposition.

The Folkman graph has a Hamiltonian cycle, and more strongly a Hamiltonian decomposition into two Hamiltonian cycles. Like every 4-regular bipartite graph, its edges can be colored with four colors (that is, it has chromatic index 4). For instance such a coloring can be obtained by using two colors in alternation for each cycle of a Hamiltonian decomposition.

Its radius is 3, its diameter is 4, and its girth is 4. It is also 4-vertex-connected and 4-edge-connected. Its treewidth and clique-width are both 5.

It has book thickness 3, but requires five pages for a "dispersable" book embedding in which each page is a matching, disproving a conjecture of Frank Bernhart and Paul Kainen that dispersable book embeddings of regular graphs need only a number of pages equal to their degree.