TOPICS
Search

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 G is constructed by making two copies of the vertex set of G (omitting the initial edge set entirely) and constructing edges u_1v_2 and v_1u_2 for every edge uv of G. The bipartite double graph is equivalent to the graph tensor product G×K_2.

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.

Gbipartite double of G
16-cell graphHaar graph H(187)
4-antiprism graphquartic vertex-transitive graph Qt48
5-antiprism graphHaar graph H(525)
Biggs-Smith graphcubic symmetric graph F_(204)A
Clebsch graphhypercube graph Q_5
complete graph K_ncrown graph K_2 square K_n^_
Coxeter graphcubic symmetric graph F_(056)C
cubic symmetric graph F_(056)Bcubic symmetric graph F_(112)A
cubic symmetric graph F_(060)Acubic symmetric graph F_(120)B
cubic symmetric graph F_(084)Acubic symmetric graph F_(168)F
cubic symmetric graph F_(108)Acubic symmetric graph F_(216)B
cubic symmetric graph F_(168)Bcubic symmetric graph F_(336)E
cubic symmetric graph F_(168)Ccubic symmetric graph F_(336)B
cubic symmetric graph F_(168)Dcubic symmetric graph F_(336)E
cubic symmetric graph F_(182)Ccubic symmetric graph F_(364)E
cubic symmetric graph F_(220)Acubic symmetric graph F_(440)A
cubic symmetric graph F_(234)Bcubic symmetric graph F_(468A)
cubic symmetric graph F_(240)Bcubic symmetric graph F_(480)B
cubic symmetric graph F_(364)Acubic symmetric graph F_(728)C
cubic symmetric graph F_(364)Bcubic symmetric graph F_(728)E
cubic symmetric graph F_(364)Ccubic symmetric graph F_(728)F
cubic symmetric graph F_(364)Dcubic symmetric graph F_(728)F
cubic symmetric graph F_(408)Acubic symmetric graph F_(816)I
cubic symmetric graph F_(408)Bcubic symmetric graph F_(816)D
cubic symmetric graph F_(448)Acubic symmetric graph F_(896)D
cubic symmetric graph F_(480)Acubic symmetric graph F_(960)B
cubic symmetric graph F_(480)Ccubic symmetric graph F_(960)B
cubic vertex-transitive graph Ct41great rhombicuboctahedral graph
cubical graph Q_32Q_3
cuboctahedral graphrolling cube graph
cycle graph C_ncycle graph C_(2n) for n odd; 2C_n for n even
dodecahedral graph GP(10,2)cubic symmetric graph F_(040)A
Doyle graph(2,6,9)-Bouwer graph
Dürer graph GP(6,2)cubic vertex-transitive graph Ct38
empty graph K^__nempty graph K^__(2n)
n-folded cube graph for n!=2,4hypercube graph Q_n
generalized Petersen graph GP(6,2)cubic vertex-transitive graph Ct38
generalized quadrangle GQ(2,1)quartic vertex-transitive graph Qt66
Kneser graph K(n,k)bipartite Kneser graph H(n,k)
Kummer graphhypercube graph Q_6
ladder graph P_2 square P_n2P_2 square P_n
ladder rung graph nP_2ladder rung graph 2nP_2
3-matchstick graph8-crossed prism graph
Möbius ladder M_n for n!=3,5prism graph Y_(2n)
net graph C_3 circledot K_1sunlet graph C_6 circledot K_1
odd graph O_4Danzer graph
odd graph O_nbipartite Kneser graph H(2n-1,n+1)
path graph P_n2P_n
pentatope graph K_5crown graph K_2 square K_5^_
Petersen graph PGP(5,2)Desargues graph GP(10,3)
prism graph Y_nprism graph Y_(2n) for n odd; 2Y_n for n even
quartic vertex-transitive graph Qt45torus grid graph C_4 square C_8
quartic vertex-transitive graph Qt65torus grid graph C_6 square C_6
rook graph K_2 square K_4tesseract graph Q_4
rook graph K_4 square K_4Kummer graph
Shrikhande graphKummer graph
square graph C_42C_4
sunlet graph C_(2k+1) circledot K_1sunlet graph C_(4k+2) circledot K_1
tesseract graph Q_42Q_4
tetrahedral graph K_4cubical graph Q_3
transposition graph T_n2T_n
triangle graph C_3cycle graph C_6
truncated tetrahedral graphNauru graph GP(12,5)
utility graph K_(3,3)2K_(3,3)
Wagner graph M_4prism graph Y_8
web graph W_nweb graph W_(2n) for n odd; 2W_n for n even

See also

Bipartite Graph, Bipartite Kneser Graph, Cycle Double Cover, Double Graph, Graph Categorical Product, Halved Graphs, Local Graph

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Bipartite Double Graph

Cite this as:

Weisstein, Eric W. "Bipartite Double Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BipartiteDoubleGraph.html

Subject classifications