"Doubling" a graph into a bipartite graph - is there a name for it?

375 Views Asked by At

Given a directed graph $\mathcal{G}=(N,A)$ with $N=\{v_1,\dots,v_n\}$, is there a standard name for the bipartite graph $\mathcal{B}=(N,N',A')$ with $N'=\{v'_1,\dots,v'_n\}$ and $A'=\{(v_i,v'_j):(v_i,v_j)\in A\}$? Basically, $\mathcal{B}$ is obtained by making two copies of the nodes of $\mathcal{G}$ and for each arc of $\mathcal{G}$ connecting the corresponding node in the first copy to the corresponding node in the second copy.

1

There are 1 best solutions below

0
On BEST ANSWER

If $\mathcal{G}$ is an undirected graph, the bipartite graph in the question is known as the bipartite double cover of $\mathcal{G}$ (and also as the Kroenecker double cover, the canonical double cover, or simply the bipartite double of $\mathcal{G}$); and is equal to the tensor product $\mathcal{G}\times{K_2}$ between $\mathcal{G}$ and the complete graph of $2$ vertices $K_2$.