Replacement product

{\displaystyle G\circ H} — The replacement product $G\circ H$ of $K 6$ and $C 5$ . source ↗

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 ${0, \dots, d - 1}.$ Let $R$ denote the replacement product of $G$ and $H$ . The vertex set of $R$ is the Cartesian product $V (G) \times V (H)$ . For each vertex $u$ in $V (G)$ and for each edge $(i, j)$ in $E (H)$ , the vertex $(u, i)$ is adjacent to $(u, j)$ in $R$ . Furthermore, for each edge $(u, v)$ in $E (G)$ , if $v$ is the $i$ th neighbor of $u$ and $u$ is the $j$ th neighbor of $v$ , the vertex $(u, i)$ is adjacent to $(v, j)$ in $R$ .

If $H$ is an $e$ -regular graph, then $R$ is an $(e + 1)$ -regular graph.

References

Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (7 August 2006). "Expander graphs and their applications". Bulletin of the American Mathematical Society. 43 (4): 439–562. doi:10.1090/S0273-0979-06-01126-8.

External links

Trevisan, Luca (7 March 2011). "CS359G Lecture 17: The Zig-Zag Product". Retrieved 16 December 2014.

[1] Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (7 August 2006). "Expander graphs and their applications". Bulletin of the American Mathematical Society. 43 (4): 439–562. doi:10.1090/S0273-0979-06-01126-8.

1