{{short description|Binary operation on mathematical graphs}}
[[File:Replacement product.svg|thumb|300px|The replacement product <math>G \circ H</math> of {{mvar|K{{sub|6}}}} and {{mvar|C{{sub|5}}}}.]]
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.<ref>{{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}}</ref>
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.
== References == {{Reflist}}
== External links == * {{cite web |url=https://lucatrevisan.wordpress.com/2011/03/07/cs359g-lecture-17-the-zig-zag-product/ |title=CS359G Lecture 17: The Zig-Zag Product |last1=Trevisan |first1=Luca |date=7 March 2011 |website= |publisher= |accessdate=16 December 2014}}
Category:Graph products
{{Graph-stub}}