TOPICS
Search

Cocktail Party Graph


CocktailPartyGraph

The cocktail party graph of order n, also called the hyperoctahedral graph (Biggs 1993, p. 17), n-octahedron graph O_n (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 nP_2^_ of the ladder rung graph nP_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.

Cocktail party graphs are distance-transitive, and hence also distance-regular. They are also antipodal.

The cocktail party graph of order n is isomorphic to the circulant graph Ci_(1,2,...,n-1)(2n). The n-cocktail party graph is also the (2n,n)-Turán graph.

Special cases are summarized in the following table.

The n-cocktail party graph has independence polynomial

 I_n(x)=1+nx(x+2)

with corresponding recurrence equation

 I_n(x)=2I_(n-1)(x)-I_(n-2)(x).

See also

Complete k-Partite Graph, Crown Graph, Glove Problem, Handshake Problem, Ladder Graph, Party Problem, Turán Graph

Explore with Wolfram|Alpha

References

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 n-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.

Referenced on Wolfram|Alpha

Cocktail Party Graph

Cite this as:

Weisstein, Eric W. "Cocktail Party Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CocktailPartyGraph.html

Subject classifications