TOPICS
Search

Complete k-Partite Graph

CompleteKPartiteGraph

A complete k-partite graph is a k-partite graph (i.e., a set of graph vertices decomposed into k disjoint sets such that no two graph vertices within the same set are adjacent) such that every pair of graph vertices in the k sets are adjacent. If there are p, q, ..., r graph vertices in the k sets, the complete k-partite graph is denoted K_(p,q,...,r). The above figure shows the complete tripartite graph K_(2,3,5).

The notation K_(m×n) is sometimes used to mean K_(n,...,n_()_(m)) (Brouwer et al. 1989, p. 478).

A graph that is complete k-partite for some k is called a complete multipartite graph (Chartrand and Zhang 2008, p. 41). Complete multipartite graphs can be recognized in polynomial time via finite forbidden subgraph characterization since complete multipartite graphs are P^__3-free (where P^__3 is the graph complement of the path graph P_3).

The complete multipartite graph of shape p, q, ... is implemented in the Wolfram Language as CompleteGraph[{p, q, ...}].

A Turán graph is a complete multipartite graph whose partite sets are as nearly equal in cardinality as possible (Gross and Yellen 2006, p. 476).

Special cases are summarized in the following table.

K_ncomplete graph
K_(m,n)complete bipartite graph
K_(1,n)star graph S_n
K_(k,m,n)complete tripartite graph
K_(1,1,1,n)(3,n)-cone graph
K_(m×1)complete graph K_m
K_(m×2)cocktail party graph mP_2^_
K_(3×2)octahedral graph
K_(4×2)16-cell graph

The complete m-partite graph K_(n_1,n_2,...,n_m) with m>=2 has a Hamilton [quasi-Hamilton] decomposition iff n_1=n_2=...=n_m and (m-1)n_1 is even [odd] (Bosák 1990, p. 124).

See also

Complete Bipartite Graph, Complete Graph, Complete Tripartite Graph, k-Partite Graph, Turán Graph

Explore with Wolfram|Alpha

References

Bosák, J. Decompositions of Graphs. New York: Springer, 1990.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Chartrand, G. and Zhang, P. Chromatic Graph Theory. Boca Raton, FL: Chapman and Hall/CRC, 2008.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 476-477, 2006.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 23, 1994.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 12, 1986.Skiena, S. "Complete k-Partite Graphs." §4.2.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 142-144, 1990.

Referenced on Wolfram|Alpha

Complete k-Partite Graph

Cite this as:

Weisstein, Eric W. "Complete k-Partite Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Completek-PartiteGraph.html

Subject classifications