mathworld.wolfram.com

Complete Tripartite Graph -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
  • ️Wed Feb 20 2008
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

A complete tripartite graph is the k=3 case of a complete k-partite graph. In other words, it is a tripartite graph (i.e., a set of graph vertices decomposed into three disjoint sets such that no two graph vertices within the same set are adjacent) such that every vertex of each set graph vertices is adjacent to every vertex in the other two sets. If there are p, q, and r graph vertices in the three sets, the complete tripartite graph (sometimes also called a complete trigraph) is denoted K_(p,q,r).

Special classes are summarized in the following table.

CompleteTripartiteGraph

Some special cases are summarized in the following table, some of which are illustrated above.

The number of Hamiltonian cycles in the graph K_(k,m,n) can be efficiently computed using a general complete k-partite graph recurrence (Horák and Tovarek 1979). A closed-form formula is also known (submitted as a problem, 2025).

See also

Complete Bipartite Graph, Complete Graph, Complete k-Partite Graph, Cone Graph, Fan Graph, k-Partite Graph

Explore with Wolfram|Alpha

References

--. Submitted problem to Amer. Math. Monthly. Feb. 2025. Chia, G. L. and Sim, K. A. "On the Skewness of the Join of Graphs." Disc. Appl. Math. 161, 2405-2409, 2013.Horák, P. and Tovarek, L. "On Hamiltonian Cycles of Complete n-Partite Graphs." Math. Slovaca 29, 43-47, 1979.

Referenced on Wolfram|Alpha

Complete Tripartite Graph

Cite this as:

Weisstein, Eric W. "Complete Tripartite Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CompleteTripartiteGraph.html

Subject classifications