Bipartite double cover

In graph theory, the bipartite double cover of an undirected graph G is a bipartite covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs, G × K₂. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of G.

It should not be confused with a cycle double cover of a graph, a family of cycles that includes each edge twice.

The bipartite double cover of G has two vertices u_i and w_i for each vertex v_i of G. Two vertices u_i and w_j are connected by an edge in the double cover if and only if v_i and v_j are connected by an edge in G. For instance, below is an illustration of a bipartite double cover of a non-bipartite graph G. In the illustration, each vertex in the tensor product is shown using a color from the first term of the product (G) and a shape from the second term of the product (K₂); therefore, the vertices u_i in the double cover are shown as circles while the vertices w_i are shown as squares.

The bipartite double cover may also be constructed using adjacency matrices (as described below) or as the derived graph of a voltage graph in which each edge of G is labeled by the nonzero element of the two-element group.

The bipartite double cover of the Petersen graph is the Desargues graph: K₂ × G(5,2) = G(10,3).

The bipartite double cover of a complete graph K_n is a crown graph (a complete bipartite graph K_n,n minus a perfect matching). In particular, the bipartite double cover of the graph of a tetrahedron, K₄, is the graph of a cube.

...
Wikipedia