TOPICS
Search

Complete Multipartite Graph

A complete multipartite graph is a graph that is a complete k-partite graph for some positive integer k (Chartrand and Zhang 2008, p. 41).

The term therefore denotes the class obtained by allowing the number k of partite sets in a complete k-partite graph to vary. If the partite sets have sizes p, q, ..., r, the graph is denoted K_(p,q,...,r).

A balanced complete multipartite graph is a complete multipartite graph whose partite sets all have the same cardinality. Equivalently, it is a complete multipartite graph of the form K_(n,...,n_()_(m)), also denoted K_(m×n).

Zarankiewicz's conjecture proposes a formula for the graph crossing number of a complete bipartite graph. For complete multipartite graphs having at least three partite sets, the following exact formulas have been proved for every positive integer n. Define

Z(m,n)=|_m/2_||_(m-1)/2_||_n/2_||_(n-1)/2_|,

where |_x_| is the floor function.

Gcr(G)reference
K_(1,2,n)|_n/2_||_(n-1)/2_|Ho (2008a)
K_(1,3,n)Z(4,n)+|_n/2_|Asano (1986)
K_(1,4,n)Z(5,n)+2|_n/2_|Ho (2009)
K_(2,2,n)2|_n/2_||_(n-1)/2_|Klešč and Schrötter (2011)
K_(2,3,n)Z(5,n)+nAsano (1986)
K_(2,4,n)6|_n/2_||_(n-1)/2_|+2nHo (2013)
K_(1,1,1,n)|_n/2_||_(n-1)/2_|Biedl et al. (2020)
K_(1,2,2,n)Z(5,n)+|_(3n)/2_|Ho (2009)
K_(2,2,2,n)6|_n/2_||_(n-1)/2_|+3nHo (2008b)
K_(1,1,1,1,n)Z(4,n)+nHo (2009)
K_(1,1,1,2,n)Z(5,n)+2nHo (2009)
K_(1,1,1,1,1,n)4|_n/2_||_(n-1)/2_|+2n+|_n/2_|+1Lü and Huang (2008)

See also

Balanced Complete Multipartite Graph, Complete Bipartite Graph, Complete k-Partite Graph, Complete Tripartite Graph, Graph Crossing Number, Zarankiewicz's Conjecture

Explore with Wolfram|Alpha

References

Asano, K. "The Crossing Number of K_(1,3,n) and K_(2,3,n)." J. Graph Th. 10, 1-8, 1986. https://doi.org/10.1002/jgt.3190100102.Biedl, T.; Chimani, M.; Derka, M.; and Mutzel, P. "Crossing Number for Graphs with Bounded Pathwidth." Algorithmica 82, 355-384, 2020. https://doi.org/10.1007/s00453-019-00653-x.Chartrand, G. and Zhang, P. Chromatic Graph Theory. Boca Raton, FL: Chapman and Hall/CRC, 2008.Ho, P. T. "The Crossing Number of K_(1,m,n)." Disc. Math. 308, 5996-6002, 2008a. https://doi.org/10.1016/j.disc.2007.11.023.Ho, P. T. "The Crossing Number of K_(2,2,2,n)." Far East J. Appl. Math. 30, 43-69, 2008b.Ho, P. T. "On the Crossing Number of Some Complete Multipartite Graphs." Utilitas Math. 79, 125-143, 2009. https://arxiv.org/abs/1310.4381.Ho, P. T. "The Crossing Number of K_(2,4,n)." Ars Combin. 109, 527-537, 2013. https://combinatorialpress.com/ars-articles/volume-109-ars-articles/the-crossing-number-of-k_24n/.Klešč, M. and Schrötter, Š. "The Crossing Numbers of Join Products of Paths with Graphs of Order Four." Discuss. Math. Graph Th. 31, 321-331, 2011. https://doi.org/10.7151/dmgt.1548.Lü, S. and Huang, Y. "The Crossing Number of K_5×S_n." J. Math. Res. Exposition 28, 445-459, 2008.

Referenced on Wolfram|Alpha

Complete Multipartite Graph

Cite this as:

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

Subject classifications