Replacement product

[[File:Replacement product.svg|thumb|300px|The replacement product $G\circ H$ of [[complete graph|Template:Mvar]] and [[cycle graph|Template:Mvar]].]]

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 Template:Mvar is a Template:Mvar-regular graph and Template:Mvar is an Template:Mvar-regular graph with vertex set Template:Math Let Template:Mvar denote the replacement product of Template:Mvar and Template:Mvar. The vertex set of Template:Mvar is the Cartesian product Template:Math. For each vertex Template:Mvar in Template:Math and for each edge Template:Math in Template:Math, the vertex Template:Math is adjacent to Template:Math in Template:Mvar. Furthermore, for each edge Template:Math in Template:Math, if Template:Mvar is the Template:Mvarth neighbor of Template:Mvar and Template:Mvar is the Template:Mvarth neighbor of Template:Mvar, the vertex Template:Math is adjacent to Template:Math in Template:Mvar.

If Template:Mvar is an Template:Mvar-regular graph, then Template:Mvar is an Template:Math-regular graph.

External links

• Template:Cite web

Template:Graph-stub