In graph theory, the replacement product of two graphs is a graph product that can be used to reduce the degree of a graph while maintaining its connectivity.
Suppose is a -regular graph and is an -regular graph with vertex set Let denote the replacement product of and . The vertex set of is the Cartesian product . For each vertex in and for each edge in , the vertex is adjacent to in . Furthermore, for each edge in , if is the th neighbor of and is the th neighbor of , the vertex is adjacent to in .
If is an -regular graph, then is an -regular graph.