The cocktail party graph of order , also called the hyperoctahedral graph (Biggs 1993, p. 17),
-octahedron
graph
(Jungerman and Ringel 1978), matching graph (Arvind et al. 2017), or Roberts
graph, is the graph consisting of two rows of paired nodes
in which all nodes but the paired ones are connected with a graph
edge. It is the graph complement of the ladder rung graph and the dual
graph of the hypercube graph . It is also the skeleton of
the -cross polytope (which is the origin of its designation
as a hyperoctahedral graph by some authors).
It is the complete n-partite graph andis also variously
denoted
(e.g., Brouwer et al. 1989, pp. 222-223) and (e.g., Stahl 1978; White 2001, p. 59).
Arvind, V.; Köbler, J.; Rattan, G.; and Verbitsky, O. "On the Power of Color Refinement." In Fundamentals of Computation
Theory. FCT 2015 (Ed. A. Kosowski and I. Walukiewicz). Cham, Switzerland:
Springer, pp. 339-350, 2015.Ball, W. W. R. and Coxeter,
H. S. M. Mathematical
Recreations and Essays, 13th ed. New York: Dover, p. 278, 1987.Biggs,
N. L. Algebraic
Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 17
and 68, 1993.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A.
Distance-Regular
Graphs. New York: Springer-Verlag, 1989.Jungerman, M. and Ringel,
G. "The Genus of the -Octahedron: Regular Cases." J. Graph Th.2,
69-75, 1978.Roberts, F. S. "On the Boxicity and Cubicity of
a Graph." In Recent Progress in Combinatorics. New York: Academic Press,
pp. 301-310, 1969.Stahl, S. "The Embedding of a Graph--A Survey."
J. Graph Th.2, 275-298, 1978.White, A. T. "Imbedding
Problems in Graph Theory." Ch. 6 in Graphs of Groups on Surfaces: Interactions
and Models (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, pp. 49-72,
2001.