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?

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

What you are looking for is the bipartite double cover.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.