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).
This graph arises in the handshake problem.
Cocktail party graphs are distance-transitive, and hence also distance-regular. They are also antipodal.
The cocktail party graph of order 
is isomorphic to the circulant
graph 
.
The 
-cocktail
party graph is also the 
-Turán graph.
Special cases are summarized in the following table.
 |  -cocktail party graph |
| 1 | empty graph  |
| 2 | square graph  |
| 3 | octahedral graph |
| 4 | 16-cell graph |
The 
-cocktail
party graph has independence polynomial
 |
with corresponding recurrence equation
 |
-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.