Folkman graph

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.Template:R It is named after Jon Folkman, who constructed it for this property in 1967.Template:R

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.

Construction

Using modular arithmetic

Semi-symmetric graphs are defined as regular graphs (that is, graphs in which all vertices touch equally many edges) in which each two edges are symmetric to each other, but some two vertices are not symmetric. Jon Folkman was inspired to define and research these graphs in a 1967 paper, after seeing an unpublished manuscript by E. Dauber and Frank Harary which gave examples of graphs meeting the symmetry condition but not the regularity condition. Folkman's original construction of this graph was a special 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 $2r$-regular graph with $2pr$ vertices. The Folkman graph is the result of this construction for $p=5$ and $r=2$.Template:R

In more detail, for $p$ and $r$ meeting these conditions, Folkman defines a graph whose vertices are the triples $$\{(b,i,x)\mid b\in \{0,1\},i\in \{0,1,\dots ,r-1\},x\in \{0,1,\dots ,p-1\}\},$$ and whose edges connect each triple $(0,i,x)$ to the $2r$ triples of the form $(1,j,x)$ and $(1,j,x+r^{i}modp)$. For the Folkman graph with $p=5$ and $r=2$, Folkman arranges the 20 vertices of the graph in five nested squares, corresponding to the five possible values of the $x$-coefficients of these vertices. The edges from $(0,i,x)$ to $(1,j,x)$ form the sides of each square, the edges from $(0,0,x)$ to $(1,j,x+1mod5)$ connect consecutive squares and the innermost and outermost square, and the edges from $(0,1,x)$ to $(1,j,x+2mod5)$ connect squares that are not consecutive.Template:R Template:-

Subdivided double

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$.

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. This is an example of a general construction called the subdivided double.Template:R

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 Template:Nowrap Every 4-regular semi-symmetric graph in which some two vertices have the same neighborhood can be constructed in the same way, by subdividing and then doubling a 4-regular symmetric graph such as $K_5$ or the graph of the octahedron. However, there also exist larger 4-regular semi-symmetric graphs that do not have any twin vertices.Template:R

Properties

Basics

The Folkman graph has 20 vertices and 40 edges. Each vertex is incident to four edges, making it a quartic graph.Template:R

Its radius is 3 and its diameter is 4. If $v$ is one of the doubled vertices of the $K_5$ construction, then all other vertices are at most three steps away from $v$. However, there are pairs of subdivision vertices from the construction (coming from disjoint edges of $K_5$) that are four steps apart from each other.Template:R

Because the graph contains many 4-cycles, but no triangles, its girth is 4, the minimum possible for a bipartite graph.Template:R It is also 4-vertex-connected and 4-edge-connected.Template:R

Symmetry

The automorphism group of the Folkman graph (its group of symmetries) combines the $5!$ symmetries of $K_5$, acting on pairs of doubled vertices, with the $2^5$ ways of swapping doubled vertices within pairs, 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.Template:R 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.Template:R

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.Template:R

Drawings and embeddings

The Folkman graph has genus 3: it can be embedded on a triple torus, but not on any simpler oriented surface.Template:R 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.Template:R

The Folkman graph is not a 1-planar graph. This means that every graph drawing of it in the plane has at least one edge crossed by two or more other edges.Template:R

Other

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.

If follows from its construction as a subdivided double that the Folkman graph has a Hamiltonian cycle, and that every Hamiltonian cycle is complementary to another Hamiltonian cycle, forming a Hamiltonian decomposition into two Hamiltonian cycles.Template:R

Like every bipartite graph, its chromatic number is two, and its chromatic index (the minimum number of colors needed to color its edges so that no two edges of the same color meet at a vertex) equals its maximum degree, four.Template:R

The characteristic polynomial of the Folkman graph is $(x-4)x^{10}(x+4)(x^2-6{)}^4$.Template:R Expanding each vertex on one side of its bipartition by replacing it with a 5-clique, and replacing each vertex on the other side of the bipartition by a 4-vertex independent set, produces two different 20-regular 90-vertex graphs depending on which side is replaced in which way. These two graphs are isospectral graphs with high vertex connectivity and expansion.Template:R

The treewidth and clique-width of the Folkman graph are both 5.Template:R