Bipartite Double Graph

The bipartite double graph, also called the Kronecker cover, Kronecker double cover, bipartite double cover, canonical double cover, or bipartite double, of a given graph  is constructed by making two copies of the vertex set of  (omitting the initial edge set entirely) and constructing edges  and  for every edge  of . The bipartite double graph is equivalent to the graph categorical product .

In a non-bipartite connected graph, exactly one double cover is bipartite. However, a bipartite or disconnected graph may have more than one bipartite double graph, leading Pisanski (2018) to suggest than one of the alternate names should be used for this concept.

Note that the bipartite double differs from the plain double graph in that the initial edge set is discarded in the bipartite double graph, while it is retained in the double graph.

The following table summarizes bipartite double graphs for some named graphs and classes of graphs.

	bipartite double of
16-cell graph	Haar graph
4-antiprism graph	quartic vertex-transitive graph Qt48
5-antiprism graph	Haar graph
Biggs-Smith graph	cubic symmetric graph
Clebsch graph	hypercube graph
complete graph	crown graph
Coxeter graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic symmetric graph	cubic symmetric graph
cubic vertex-transitive graph Ct41	great rhombicuboctahedral graph
cubical graph
cuboctahedral graph	rolling cube graph
cycle graph	cycle graph  for  odd;  for  even
dodecahedral graph	cubic symmetric graph
Doyle graph	-Bouwer graph
Dürer graph	cubic vertex-transitive graph Ct38
empty graph	empty graph
-folded cube graph for	hypercube graph
generalized Petersen graph	cubic vertex-transitive graph Ct38
generalized quadrangle	quartic vertex-transitive graph Qt66
Kneser graph	bipartite Kneser graph
Kummer graph	hypercube graph
ladder graph
ladder rung graph	ladder rung graph
3-matchstick graph	8-crossed prism graph
Möbius ladder  for	prism graph
net graph	sunlet graph
odd graph	bipartite Kneser graph
path graph
pentatope graph	crown graph
Petersen graph	Desargues graph
prism graph	prism graph  for  odd;  for  even
quartic vertex-transitive graph Qt45	torus grid graph
quartic vertex-transitive graph Qt65	torus grid graph
rook graph	tesseract graph
rook graph	Kummer graph
Shrikhande graph	Kummer graph
square graph
sunlet graph	sunlet graph
tesseract graph
tetrahedral graph	cubical graph
transposition graph
triangle graph	cycle graph
truncated tetrahedral graph	Nauru graph
utility graph
Wagner graph	prism graph
web graph	web graph  for  odd;  for  even

REFERENCES

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, pp. 17 and 24, 1989.

DistanceRegular.org. "Bipartite Doubles." http://www.distanceregular.org/indexes/bipartitedoubles.html.Pisanski, T. "Not Every Bipartite Double Cover Is Canonical." Bull. ICA 82, 51-55, 2018.