Replacement product
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.