Bipartite double cover

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

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

Construction

The bipartite double cover of Template:Mvar has two vertices Template:Mvar and Template:Mvar for each vertex Template:Mvar of Template:Mvar. Two vertices Template:Mvar and Template:Mvar are connected by an edge in the double cover if and only if Template:Mvar and Template:Mvar are connected by an edge in Template:Mvar. For instance, below is an illustration of a bipartite double cover of a non-bipartite graph Template:Mvar. In the illustration, each vertex in the tensor product is shown using a color from the first term of the product (Template:Mvar) and a shape from the second term of the product (Template:Math); therefore, the vertices Template:Mvar in the double cover are shown as circles while the vertices Template:Mvar 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 Template:Mvar is labeled by the nonzero element of the two-element group.

Examples

The bipartite double cover of the Petersen graph is the Desargues graph: Template:Math.

The bipartite double cover of a complete graph Template:Mvar is a crown graph (a complete bipartite graph Template:Math minus a perfect matching). In particular, the bipartite double cover of the graph of a tetrahedron, Template:Math, 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.

Matrix interpretation

If an undirected graph Template:Mvar has a matrix Template:Mvar as its adjacency matrix, then the adjacency matrix of the double cover of Template:Mvar is

$\left[\begin{array}{cc}0& A\\ A^T& 0\end{array}\right],$

and the biadjacency matrix of the double cover of Template:Mvar is just Template:Mvar itself. That is, the conversion from a graph to its double cover can be performed simply by reinterpreting Template:Mvar as a biadjacency matrix instead of as an adjacency matrix. More generally, the reinterpretation the adjacency matrices of directed graphs as biadjacency matrices provides a combinatorial equivalence between directed graphs and balanced bipartite graphs.

Properties

The bipartite double cover of any graph Template:Mvar is a bipartite graph; both parts of the bipartite graph have one vertex for each vertex of Template:Mvar. A bipartite double cover is connected if and only if Template:Mvar is connected and non-bipartite.

The bipartite double cover is a special case of a double cover (a 2-fold covering graph). A double cover in graph theory can be viewed as a special case of a topological double cover.

If Template:Mvar is a non-bipartite symmetric graph, the double cover of Template:Mvar is also a symmetric graph; several known cubic symmetric graphs may be obtained in this way. For instance, the double cover of Template:Math is the graph of a cube; the double cover of the Petersen graph is the Desargues graph; and the double cover of the graph of the dodecahedron is a 40-vertex symmetric cubic graph.

It is possible for two different graphs to have isomorphic bipartite double covers. For instance, the Desargues graph is not only the bipartite double cover of the Petersen graph, but is also the bipartite double cover of a different graph that is not isomorphic to the Petersen graph. Not every bipartite graph is a bipartite double cover of another graph; for a bipartite graph Template:Mvar to be the bipartite cover of another graph, it is necessary and sufficient that the automorphisms of Template:Mvar include an involution that maps each vertex to a distinct and non-adjacent vertex. For instance, the graph with two vertices and one edge is bipartite but is not a bipartite double cover, because it has no non-adjacent pairs of vertices to be mapped to each other by such an involution; on the other hand, the graph of the cube is a bipartite double cover, and has an involution that maps each vertex to the diametrally opposite vertex. An alternative characterization of the bipartite graphs that may be formed by the bipartite double cover construction was obtained by Template:Harvtxt.

Name

In a connected graph that is not bipartite, only one double cover is bipartite, but when the graph is bipartite or disconnected there may be more than one. For this reason, Tomaž Pisanski has argued that the name "bipartite double cover" should be deprecated in favor of the "canonical double cover" or "Kronecker cover", names which are unambiguous.Template:Sfnp

Other double covers

In general, a graph may have multiple double covers that are different from the bipartite double cover.

1. The graph Template:Mvar is a covering graph of Template:Mvar if there is a surjective local isomorphism Template:Mvar from Template:Mvar to Template:Mvar. In the figure, the surjection is indicated by the colours. For example, Template:Mvar maps both blue nodes in Template:Mvar to the blue node in Template:Mvar. Furthermore, let Template:Mvar be the neighbourhood of a blue node in Template:Mvar and let Template:Mvar be the neighbourhood of the blue node in Template:Mvar; then the restriction of Template:Mvar to Template:Mvar is a bijection from Template:Mvar to Template:Mvar. In particular, the degree of each blue node is the same. The same applies to each colour.
2. The graph Template:Mvar is a double cover (or 2-fold cover or 2-lift) of Template:Mvar if the preimage of each node in Template:Mvar has size 2. In the example, there are exactly 2 nodes in Template:Mvar that are mapped to the blue node in Template:Mvar.

In the following figure, the graph Template:Mvar is a double cover of the graph Template:Mvar:

However, Template:Mvar is not the bipartite double cover of Template:Mvar or any other graph; it is not a bipartite graph.

If we replace one triangle by a square in Template:Mvar the resulting graph has four distinct double covers. Two of them are bipartite but only one of them is the Kronecker cover.

As another example, the graph of the icosahedron is a double cover of the complete graph Template:Math; to obtain a covering map from the icosahedron to Template:Math, map each pair of opposite vertices of the icosahedron to a single vertex of Template:Math. However, the icosahedron is not bipartite, so it is not the bipartite double cover of Template:Math. Instead, it can be obtained as the orientable double cover of an embedding of Template:Math on the projective plane.

The double covers of a graph correspond to the different ways to sign the edges of the graph.

See also

• Bipartite half

References

• Template:Citation.
• Template:Citation. The “coverings” in the title of this paper refer to the vertex cover problem, not to bipartite double covers. However, Template:Harvtxt cite this paper as the source of the idea of reinterpreting the adjacency matrix as a biadjacency matrix.
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation.

External links

• Template:Mathworld