4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ $G'$ is isomorphic to $G\otimes K_2$, where $\otimes$ is the tensor product. $\endgroup$
    – Moh514
    Commented Sep 3, 2015 at 14:20

1 Answer 1

Reset to default
6
$\begingroup$

What you are looking for is the bipartite double cover.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .