hyperoctahedral graph | matching graph | roberts graph

The cocktail party graph of order n, also called the hyperoctahedral graph, n-octahedron graph O_n, n-dimensional octahedron , matching graph , 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 (n P_2)^_ of the ladder rung graph n P_2 and the dual graph of the hypercube graph Q_n. It is also the skeleton of the n-cross polytope (which is the origin of its designation as a hyperoctahedral graph by some authors). It is the complete n-partite graph K_(2, ..., 2_︸_n) andis also variously denoted K_(n×2) (e.g., Brouwer et al. 1989, pp. 222-223) and K_(n(2)) (e.g., Stahl 1978; White 2001, p. 59). This graph arises in the handshake problem.

complete k-partite graph | crown graph | glove problem | handshake problem | ladder graph | party problem | Turán graph