Subdivided double

The Folkman graph (red subdivision vertices and blue doubled vertices) as the subdivided double of a five-vertex complete graph (yellow)

In graph theory, the subdivided double is a construction used to transform a 4-regular graph into a larger 4-regular graph. It consists of two steps: subdividing every edge into a path of two edges (with a new vertex in the middle of each path), and then replacing every vertex of the original graph with two copies, both adjacent to the same subdivision vertices. Potočnik, Verret, and Wilson use the notation $\operatorname {SDD} (G)$ to denote the subdivided double of a graph $G$. It was named as the subdivided double earlier, by Potočnik and Wilson.

An example of a subdivided double is the Folkman graph, a ten-vertex graph that can be constructed from the five-vertex complete graph $K_{5}$ as its subdivided double $\operatorname {SDD} (K_{5})$.

Every subdivided double is a bipartite graph, with the subdivision vertices on one side of its bipartition and the doubled vertices on the other side. When the starting graph $G$ is an arc-transitive graph (having symmetries mapping any two oriented edges to each other), the subdivided double $\operatorname {SDD} (G)$ is an edge-transitive graph: the subdivided double has symmetries that map any two edges to each other. However, it may not be arc-transitive or vertex-transitive: there may be no symmetry that swaps the two sides of the bipartition. For this reason, the subdivided double construction has been studied as a way of generating semi-symmetric graphs, bipartite graphs that are edge-transitive but not vertex-transitive. Every subdivided double has exponentially many Hamiltonian cycles, and in a subdivided double every Hamiltonian cycle is complementary to another Hamiltonian cycle, forming a Hamiltonian decomposition.

Whenever a 4-regular semi-symmetric graph contains two twin vertices, vertices that have the same sets of neighbors as each other, it can be constructed as a subdivided double.