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 n-partite graph K_(m_1,m_2,...,m_n) with n>=2 has a Hamilton [quasi-Hamilton] decomposition iff m_1=m_2=...=m_n and (n-1)m_1 is even [odd] (Bosák 1990, p. 124).

A complete k-partite graph K_(m_1,m_2,...,m_n) is Hamiltonian iff

sum_(i!=j)m_i>=m_j

for j=1, ..., n, a result which follows from Pósa's theorem (Horák and Tovarek 1979).

Singmaster (1975) counted Hamiltonian cycles with a marked starting node on the cocktail party graph K_(2,2,2,...), Horák and Tovarek (1979) gave a recursive formula for the number of Hamiltonian cycles of an arbitrary complete k-partite graph, and Krasko et al. (2017) enumerated Hamiltonian cycles on complete k-partite graphs K_(n,n,n,...).

Letting H(m_1,...,m_n) be the number of Hamiltonian cycles in the graph K_(m_1,...,m_n) with n>=2, the concise and elegant recurrence formula of Horák and Tovarek (1979) states

H(m_1+1,m_2,...,m_n)=(sum_(i=1)^nm_i-2m_1)H(m_1,m_2,...,m_n)+sum_(i=2)^nm_i(m_i-1)H(m_1,m_2,...,m_i-1,...,m_n),

together with initial values H(n,n)=(n-1)!n!/2, H(m,n)=0 for m!=n, H(1,1,1)=H(1,1,2)=1, and H(1,1,1,1)=3. This recurrence can be implemented efficiently using memoization combined with sorting of indices in the second term and removal of any zero indices in both terms.

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.Horák, P. and Tovarek, L. "On Hamiltonian Cycles of Complete n-Partite Graphs." Math. Slovaca 29, 43-47, 1979.Krasko, E.; Labutin, I.; and Omelchenko, A. "Enumeration of Labelled and Unlabelled Hamiltonian Cycles in Complete k-partite Graphs." 1 Sep 2017. https://arxiv.org/abs/1709.03218.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 12, 1986.Singmaster, D. "Hamiltonian Circuits on the n-dimensional Octahedron." J. Combin. Th., Ser. B 19, 1-4, 1975.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