Properties
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. 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. 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 graph with two vertices and one edges 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 Sampathkumar (1975).
Read more about this topic: Bipartite Double Cover
Famous quotes containing the word properties:
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)