The cocktail party graph of order , also called the hyperoctahedral graph (Biggs 1993, p. 17),
-octahedron
graph
(Jungerman and Ringel 1978),
-dimensional octahedron (Singmaster 1975, Krasko et al.
2017), 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.
1 | empty graph |
2 | square graph |
3 | octahedral graph |
4 | 16-cell graph |
The -cocktail
party graph has independence polynomial
(1)
|
with corresponding recurrence equation
(2)
|
Singmaster (1975) counted Hamiltonian cycles with a marked starting node on the cocktail party graph. When dividing by to get the number of undirected and unmarked Hamiltonian
cycles, his result is given as a sum which can be expressed in closed form
(3)
| |||
(4)
|
in terms of the gamma function and confluent
hypergeometric function of the first kind
.