Not every bipartite graph is a bipartite double cover of another graph for a bipartite graph G to be the bipartite cover of another graph, it is necessary and sufficient that the automorphisms of G include an involution that maps each vertex to a distinct and non-adjacent vertex. 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. It is possible for two different graphs to have isomorphic bipartite double covers. For instance, the double cover of K 4 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. 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. A double cover in graph theory can be viewed as a special case of a topological double cover. The bipartite double cover is a special case of a double cover (a 2-fold covering graph). A bipartite double cover is connected if and only if G is connected and non-bipartite.
The bipartite double cover of any graph G is a bipartite graph both parts of the bipartite graph have one vertex for each vertex of G. More generally, the reinterpretation the adjacency matrices of directed graphs as biadjacency matrices provides a combinatorial equivalence between directed graphs and balanced bipartite graphs. 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.
, Īnd the biadjacency matrix of the double cover of G is just A itself. If an undirected graph G has a matrix A as its adjacency matrix, then the adjacency matrix of the double cover of G is 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. 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 a complete graph K n is a crown graph (a complete bipartite graph K n, n minus a perfect matching). The bipartite double cover of the Petersen graph is the Desargues graph: K 2 × G(5,2) = G(10,3). 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. 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. For instance, below is an illustration of a bipartite double cover of a non-bipartite graph 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. The bipartite double cover of G has two vertices u i and w i for each vertex v i of G.
0 kommentar(er)
