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 G is a d-regular graph and H is an e-regular graph with vertex set. Let R denote the replacement product of G and H. The vertex set of R is the Cartesian product V × V. For each vertex u in V and for each edge in E, the vertex is adjacent to in R. Furthermore, for each edge in E, if v is the ith neighbor of u and u is the jth neighbor of v, the vertex is adjacent to in R.
If H is an e-regular graph, then R is an -regular graph.
