Cocktail Party Graph

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.

	-cocktail party graph
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)

The -cocktail party graph is conjectured to have graph genus

(3)

a result that has been proved for (Jungerman and Ringel 1978, White 2001, Metzger and Ulrigg 2025).

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

			(4)
			(5)

in terms of the gamma function and confluent hypergeometric function of the first kind .