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.Template:R Potočnik, Verret, and Wilson use the notation $\mathrm{SDD}(G)$ to denote the subdivided double of a graph $G$.Template:R It was named as the subdivided double earlier, by Potočnik and Wilson.Template:R

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 $\mathrm{SDD}(K_5)$.Template:R

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.Template:R When the starting graph $G$ is an arc-transitive graph (having symmetries mapping any two oriented edges to each other), the subdivided double $\mathrm{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.Template:R 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.Template:R

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