A complete 
-partite
graph is a k-partite graph (i.e., a set
of graph vertices decomposed into 
disjoint sets such that no two graph
vertices within the same set are adjacent) such that every pair of graph
vertices in the 
sets are adjacent. If there are 
, 
, ..., 
graph vertices in the 
sets, the complete 
-partite graph is denoted 
. The above figure shows the complete
tripartite graph 
.
The notation 
is sometimes used to mean 
(Brouwer et al. 1989, p. 478).
A graph that is complete 
-partite for some 
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 
-free (where 
is the graph complement
of the path graph 
).
A non-empty graph is a complete multipartite graph iff it does not have 
as an induced subgraph, its graph
complement does not have 
as an induced subgraph, or the connected
components of its graph complement are all
complete graphs. In the last case, the sizes of
the connected components of the complement give the sizes of the 
-partition.
The complete multipartite graph of shape 
, 
, ... 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.
The complete 
-partite
graph 
with 
has a Hamilton [quasi-Hamilton] decomposition iff 
and 
is even [odd] (Bosák 1990, p. 124).
A complete 
-partite
graph 
is Hamiltonian iff
for 
,
..., 
,
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 
,
Horák and Tovarek (1979) gave a recursive formula for the number of Hamiltonian
cycles of an arbitrary complete 
-partite graph, and Krasko et al. (2017) enumerated
Hamiltonian cycles on complete 
-partite graphs 
.
Letting 
be the number of Hamiltonian cycles in the graph
with 
,
the concise and elegant recurrence formula of Horák and Tovarek (1979) states
together with initial values 
for 
and 
(and 0 otherwise), 
, and 
. 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 
-Partite Graphs." Math. Slovaca 29, 43-47,
1979.Krasko, E.; Labutin, I.; and Omelchenko, A. "Enumeration of
Labelled and Unlabelled Hamiltonian Cycles in Complete 
-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 
-dimensional Octahedron." J. Combin. Th., Ser. B 19,
1-4, 1975.Skiena, S. "Complete 
-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
Cite this as:
Weisstein, Eric W. "Complete k-Partite Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Completek-PartiteGraph.html