Bipartite double cover
Encyclopedia
In graph theoretic mathematics
, 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 × K2. 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 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
.
is the Desargues graph
: K2 × G(5,2) = G(10,3).
The bipartite double cover of a complete graph
Kn is a crown graph
(a complete bipartite graph
Kn,n minus a perfect matching). In particular, the bipartite double cover of the graph of a tetrahedron
, K4, 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.
, 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. That is, the conversion from a graph to its double cover can be performed simply by reinterpreting A as a biadjacency matrix instead of as an adjacency matrix. More generally, the reinterpretation the adjacency matrices of directed graph
s as biadjacency matrices provides a combinatorial equivalence
between directed graphs and balanced bipartite graphs.
; both parts of the bipartite graph have one vertex for each vertex of G. A bipartite double cover is connected if and only if G 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 G is a non-bipartite symmetric graph
, the double cover of G is also a symmetric graph; several known cubic
symmetric graphs may be obtained in this way. For instance, the double cover of K4 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. A characterization of the bipartite graphs that may be formed by the bipartite double cover construction was obtained by .
However, C is not a bipartite double cover of H or any other graph; it is not a bipartite graph.
As another example, the graph of the icosahedron
is a double cover of the complete graph K6; to obtain a covering map from the icosahedron to K6, map each pair of opposite vertices of the icosahedron to a single vertex of K6. However, the icosahedron is not bipartite, so it is not the bipartite double cover of K6. Instead, it can be obtained as the orientable double cover of an embedding
of K6 on the projective plane
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the bipartite double cover of an undirected graph G is a bipartite
Bipartite
Bipartite means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:-Mathematics:* 2 * bipartite graph* bipartite cubic, a type of cubic function-Medicine:...
covering graph
Covering graph
In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G...
of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs
Tensor product of graphs
In graph theory, the tensor product G × H of graphs G and H is a graph such that* the vertex set of G × H is the Cartesian product V × V; and...
G × K2. 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.
Construction
The bipartite double cover of G has two vertices ui and wi for each vertex vi of G. Two vertices ui and wj are connected by an edge in the double cover if and only if vi and vj 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 (K2); therefore, the vertices ui in the double cover are shown as circles while the vertices wi 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
Voltage graph
In graph-theoretic mathematics, a voltage graph is a directed graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used in topological graph theory as a concise way to specify another graph called the derived graph of the...
in which each edge of G is labeled by the nonzero element of the two-element group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
.
Examples
The bipartite double cover of the Petersen graphPetersen graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...
is the Desargues graph
Desargues graph
In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Gérard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial...
: K2 × G(5,2) = G(10,3).
The bipartite double cover of a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
Kn is a crown graph
Crown graph
In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j...
(a complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
Kn,n minus a perfect matching). In particular, the bipartite double cover of the graph of a tetrahedron
Tetrahedron
In geometry, a tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids...
, K4, is the graph of a cube
Cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. The cube can also be called a regular hexahedron and is one of the five Platonic solids. It is a special kind of square prism, of rectangular parallelepiped and...
.
The bipartite double cover of an odd-length cycle graph
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
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 G has a matrix A as its adjacency matrixAdjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
, 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. That is, the conversion from a graph to its double cover can be performed simply by reinterpreting A as a biadjacency matrix instead of as an adjacency matrix. More generally, the reinterpretation the adjacency matrices of directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s as biadjacency matrices provides a combinatorial equivalence
Bijective proof
In combinatorics, bijective proof is a proof technique that finds a bijective function f : A → B between two sets A and B, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of...
between directed graphs and balanced bipartite graphs.
Properties
The bipartite double cover of any graph G is a bipartite graphBipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
; both parts of the bipartite graph have one vertex for each vertex of G. A bipartite double cover is connected if and only if G is connected and non-bipartite.
The bipartite double cover is a special case of a double cover (a 2-fold covering graph
Covering graph
In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G...
). A double cover in graph theory can be viewed as a special case of a topological double cover.
If G is a non-bipartite symmetric graph
Symmetric graph
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
, the double cover of G is also a symmetric graph; several known cubic
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
symmetric graphs may be obtained in this way. For instance, the double cover of K4 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
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
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. A characterization of the bipartite graphs that may be formed by the bipartite double cover construction was obtained by .
Other double covers
In general, a graph may have multiple double covers that are different from the bipartite double cover. In the following figure, the graph C is a double cover of the graph H:- The graph C is a covering graph of H: there is a surjective local isomorphism f from C to H, the one indicated by the colours. For example, f maps both blue nodes in C to the blue node in H. Furthermore, let X be the neighbourhoodNeighbourhood (graph theory)In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. For example, the image shows a...
of a blue node in C and let Y be the neighbourhood of the blue node in H; then the restriction of f to X is a bijection from X to Y. In particular, the degree of each blue node is the same. The same applies to each colour. - The graph C is a double cover (or 2-fold cover or 2-lift) of H: the preimage of each node in H has size 2. For example, there are exactly 2 nodes in C that are mapped to the blue node in H.
However, C is not a bipartite double cover of H or any other graph; it is not a bipartite graph.
As another example, the graph of the icosahedron
Icosahedron
In geometry, an icosahedron is a regular polyhedron with 20 identical equilateral triangular faces, 30 edges and 12 vertices. It is one of the five Platonic solids....
is a double cover of the complete graph K6; to obtain a covering map from the icosahedron to K6, map each pair of opposite vertices of the icosahedron to a single vertex of K6. However, the icosahedron is not bipartite, so it is not the bipartite double cover of K6. Instead, it can be obtained as the orientable double cover of an embedding
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
of K6 on the projective plane
Projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines that do not intersect...
.