TOPICS
Search

Complete Tripartite Graph Minus Perfect Matching

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
CompleteTripartiteGraphMinusPerfectMatching

Unlike the complete graph K_(2n) minus a perfect matching giving K_(2n)-M, which is known as the cocktail party graph, and the complete bipartite graph K_(n,n) minus a perfect matching giving K_(n,n)-M, which is known as the crown graph, the complete tripartite graph K_(2n,2n,2n) minus a perfect matching does not appear to have a special name.

K_(2,2,2)-M is the 3-prism graph.

The numbers of perfect matchings in K_(2n,2n,2n)-M for n=0, 1, ... are 1, 4, 825, 819242, 2243990201, 13077319842984, ... (OEIS A393180), which are given by the sum

sum_(i=0)^nsum_(j=0)^nsum_(k=0)^n(-1)^(i+j+k)(n; i)(n; j)(n; k)(2n-i-j; n-i)(2n-i-k; n-k)(2n-j-k; n-j)(n-i)!(n-j)!(n-k)!.

See also

Cocktail Party Graph, Complete Tripartite Graph, Crown Graph, Perfect Matching

Explore with Wolfram|Alpha

References

Johnston, D.; Mark Kayll, P.; and Palmer, C. "Deranged Matchings: Proofs and Conjectures." 30 Oct 2022. https://arxiv.org/abs/2209.11319.Sloane, N. J. A. Sequence A393180 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Complete Tripartite Graph Minus Perfect Matching." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CompleteTripartiteGraphMinusPerfectMatching.html

Subject classifications