# Method to construct a bipartite graph G' with 2n vertices from a graph G

I have seen mentioned in a talk an operation that takes a graph $G=(V,E)$ and constructs a new bipartite graph $G'=(V',E')$ such that $V' = V\times \{0,1\}$ and $E'=\{((i,1),(j,0)) : (i,j)\in E\} \cup \{((i,0),(j,1)) : (i,j)\in E\}$.

In words, one takes two copies of the vertices of the graph, and makes the edges go from copy A to copy B and vice versa. The new graph has $2|V|$ vertices, $2|E|$ edges, and is clearly bipartite.

This operation was called bipartition, but a quick Google search for this name returns only other another more common concept (a bipartition of a bipartite graph is a decomposition of $V=V_1 \cup V_2$ such that the edges only go from $V_1$ to $V_2$ and vice versa). Unfortunately, I forgot which talk it was, so I cannot ask the speaker for more information.

Where can I find some references mentioning this operation? Does it have another more common name?

• $G'$ is isomorphic to $G\otimes K_2$, where $\otimes$ is the tensor product. – Moh514 Sep 3 '15 at 14:20