Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Bipartite double cover
Summary
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_2. 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_2); 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_2 × 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_4, is the graph of a cube.
The bipartite double cover of an odd-length cycle graph is a cycle of twice the length, while the bipartite double of any bipartite graph (such as an even length cycle, shown in the following example) is formed by two disjoint copies of the original graph.
If an undirected graph G has a matrix A as its adjacency matrix, then the adjacency matrix of the double cover of G is
and the biadjacency matrix of the double cover of G is just A itself.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.