Replacement product

{{short description|Binary operation on mathematical graphs}}

File:Replacement product.svg and cycle graph.]]

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.{{cite journal|last1=Hoory|first1=Shlomo|last2=Linial|first2=Nathan|last3=Wigderson|first3=Avi|title=Expander graphs and their applications|journal=Bulletin of the American Mathematical Society|date=7 August 2006|volume=43|issue=4|pages=439–562|doi=10.1090/S0273-0979-06-01126-8|doi-access=free}}

Suppose {{mvar|G}} is a {{mvar| d}}-regular graph and {{mvar|H}} is an {{mvar|e}}-regular graph with vertex set {{math|{0, …, d – 1}.}} Let {{mvar|R}} denote the replacement product of {{mvar|G}} and {{mvar|H}}. The vertex set of {{mvar|R}} is the Cartesian product {{math|V(G) × V(H)}}. For each vertex {{mvar|u}} in {{math|V(G)}} and for each edge {{math|(i, j)}} in {{math|E(H)}}, the vertex {{math|(u, i)}} is adjacent to {{math|(u, j)}} in {{mvar|R}}. Furthermore, for each edge {{math|(u, v)}} in {{math|E(G)}}, if {{mvar|v}} is the {{mvar|i}}th neighbor of {{mvar|u}} and {{mvar|u}} is the {{mvar|j}}th neighbor of {{mvar|v}}, the vertex {{math|(u, i)}} is adjacent to {{math|(v, j)}} in {{mvar|R}}.

If {{mvar|H}} is an {{mvar|e}}-regular graph, then {{mvar|R}} is an {{math|(e + 1)}}-regular graph.