TOPICS
Search

Complete Tripartite Graph Minus Perfect Matching

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
CompleteTripartiteGraphMinusPerfectMatching

A complete tripartite graph minus a perfect matching is a graph K_(2n,2n,2n)-M obtained by deleting the edges of a perfect matching M from the complete tripartite graph K_(2n,2n,2n), where n is a positive integer. All choices of M give isomorphic graphs.

The analogous constructions for the complete graph K_(2n) and the complete bipartite graph K_(n,n) give the cocktail party graph and the crown graph, respectively.

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

The numbers of perfect matchings in K_(2n,2n,2n)-M for n=1, 2, ... are 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

House of Graphs. Complete Tripartite Graph Minus Perfect Matching Graphs. K3 Box K2.Johnston, D.; Kayll, P. M.; and Palmer, C. "Deranged Matchings: Proofs and Conjectures." Amer. Math. Monthly 131, 95-111, 2024. https://doi.org/10.1080/00029890.2023.2274239.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