Subdivided double

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.^[1][2] Potočnik, Verret, and Wilson use the notation ${\displaystyle \operatorname {SDD} (G)}$ to denote the subdivided double of a graph ${\displaystyle G}$.^[3] It was named as the subdivided double earlier, by Potočnik and Wilson.^[1]

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

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.^[1] When the starting graph ${\displaystyle G}$ is an arc-transitive graph (having symmetries mapping any two oriented edges to each other), the subdivided double ${\displaystyle \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.^[1][2] 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.^[4]

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.^[1][2]