Can anybody tell me what is a Zig-Zag product in graph theory? I am getting no idea how this product is done and how edges are defined in the product? I have some links:
http://lucatrevisan.wordpress.com/2011/03/07/cs359g-lecture-17-the-zig-zag-product/#more-2203
http://en.wikipedia.org/wiki/Zig-zag_product
what does [[n]] x [[D]] means here? Please help in understanding the above product. Specially about the adjacency among edges. I will be really thankful. Thanks a lot.
In computer science $[n]$ usually denotes the set $\{1,2,\ldots,n\}$ and $[n]\times [D]$ is the standard Cartesian product. As I see it, the idea behind the Zig-Zag product of graphs is that we want to have something what is product-like, but with small degree.
We start with $D$-regular graph $G$ ($\color{red}{\text{red}}$) and $d$-regular graph $H$ ($\color{blue}{\text{blue}}$). Note, that on the following picture, $H$ is not 2-regular, this is wrong, but otherwise the figures would be more complex and less interesting (you can imagine that you see only a part of the graph and there are some more vertices which are not visible).
As a base we take $|V(G)|$ copies of $H$, so we have $|V(G)|\cdot|V(H)| = |V(G) \times V(H)| $ $= [n]\times [D]$ vertices total.
Now, we use the fact that $|V(H)| = D$ and that $G$ is $D$-regular, that is, we make the $i$-th vertex of $H_v$ (the copy of $H$ that corresponds to $v \in G$) responsible for the $i$-th edge of vertex $v$. Observe, that the sum of red and blue edges would give you the replacement product of $G$ and $H$.
Then we add an edge between any two vertices connected by $\color{blue}{\text{blue}}\text{-}\color{red}{\text{red}}\text{-}\color{blue}{\text{blue}}$ paths, in the following picture 3 such paths have been marked (dotted, dashed, and dot-dashed) in $\color{magenta}{\text{magenta}}$ color.
And we obtain the following graph:
Please note, again, that for sake of simplicity and readability we started with $H$ that is not regular, hence our resulting graph is not regular too (it should be for regular $H$ as each path starts with $d$ choices for blue edge, then there exists exactly one red edge, and ends with $d$ choices for another blue edge, hence $d^2$-regular).
Also, the article at French Wikipedia is much more accessible (and has nice pictures too), if you don't speak French, then try translating it.
I hope this helps $\ddot\smile$