 Zig-zag product

For a port-labeled $D$-regular graph $G$ and a $d$-regular graph $H$ on its $D$ port labels, replace every vertex by a copy of $H$. An edge makes a step in $H$, crosses the corresponding edge of $G$, then makes another step in $H$. The result has $|G|D$ vertices and degree $d^2$. Its normalized operator is $BRB$, where $B=I\otimes P_H$ and $R$ is the involutive edge rotation of $G$. Decomposing a mean-zero vector into cloud-constant and cloud-orthogonal parts proves the bound $\rho (G\mathrm{zigzag}H)\le \rho (G)+2\rho (H)+\rho (H{)}^2$.

The zig-zag product is an operation on graphs, specifically useful in the field of combinatorial design and expander graphs. It allows the construction of a new graph from two existing graphs in a way that preserves certain properties, typically expanding size and connectivity characteristics. For two graphs \( G \) and \( H \): - Let \( G \) be a graph with vertex set \( V_G \) and \( H \) be a directed graph with vertex set \( V_H \).