TOPICS
Search

Halved Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

For a connected bipartite graph G, the halved graph G^+ and G^- are the two connected components of the distance 2-graph of G.

The following table summarizes some named graphs and halved graph pairs

graphhalved graphs
A graphtriangle graph C_3
bipartite Kneser graph H(7,3)7-tetrahedral Johnson graph
(4,6)-cagecomplete graph K_(13)
complete bipartite graph K_(n,n)complete graph K_n
2n-crossed prism graph2n-circulant graph Ci_(2n)(1,n-1,n)
crown graphcomplete graph K_n
Nauru graphcirculant graph Ci_(12)(1,2,5)
cubic symmetric graph F_(026)A13-Paley graph
cubic symmetric graph F_(038)A19-cyclotomic graph
cubic symmetric graph F_(090)Ahalved Foster graph
cubical graph Q_3tetrahedral graph
cycle graph C_(2n)cycle graph C_n
Desargues graph5-triangular graph
Dyck graphShrikhande graph
Franklin graphcomplete graph K_6
great rhombicosidodecahedral graphsnub dodecahedral graph
great rhombicuboctahedral graphsnub cubical graph
(8,1)-Hadamard graphcocktail party graph K_(8×2)
(12,1)-Hadamard graphcocktail party graph K_(12×2)
(16,1)-Hadamard graphcocktail party graph K_(16×2)
(16,2)-Hadamard graphcocktail party graph K_(16×2)
(16,3)-Hadamard graphcocktail party graph K_(16×2)
(16,4)-Hadamard graphcocktail party graph K_(20×2)
(20,1)-Hadamard graphcocktail party graph K_(20×2)
(20,2)-Hadamard graphcocktail party graph K_(20×2)
(20,3)-Hadamard graphcocktail party graph K_(20×2)
Heawood graphcomplete graph K_7
H graphtriangle graph C_3
bipartite double of the Hoffman-Singleton graphHoffman-Singleton graph complement
hypercube graph Q_nn-halved cube graph
Kummer graphcomplete graph K_(16)
Tutte 8-cagegeneralized quadrangle GQ(2,2)
Möbius-Kantor graph16-cell graph
(2n+1)-Möbius laddercirculant graph Ci_(2n+1)(1,2)
Pappus graphcomplete tripartite graph K_(3,3,3)
2n-prism graphn-antiprism graph
Reye configurationcomplete graph K_(12)
rolling cube graphcocktail party graph K_(6×2)
square graphpath graph P_2
sunlet graph C_4 circledot K_1diamond graph
sunlet graph C_6 circledot K_12-Sierpiński gasket graph
tesseract graph16-cell graph
truncated octahedral graphicosahedral graph
utility graphtriangle graph C_3

See also

Bipartite Double Graph, Distance k-Graph, Double Graph, Halved Cube Graph

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

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

Referenced on Wolfram|Alpha

Halved Graphs

Cite this as:

Weisstein, Eric W. "Halved Graphs." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HalvedGraphs.html