complete k-partite graph

A complete k-partite graph is a maximal k-partite graph. In other words, a graph is complete k-partite provided that its vertex set admits a partition $V=V_{1}\sqcup\dots\sqcup V_{k}$ such that for any $u\in V_{i}$ and $v\in V_{j}$ , uv is an edge if and only if $i\neq j$ .

For any tuple $(a_{1},\dots,a_{k})$ , there is up to graph isomorphism a single complete k-partite graph with maximal stable sets $V_{1},\dots,V_{k}$ such that for each $i$ , there are exactly $a_{i}$ vertices in $V_{i}$ . This graph is denoted by $K_{a_{1},\dots,a_{k}}$ .

Below we display the 3-partite complete graph $K_{2,3,4}$ :

\xymatrix{&{\color[rgb]{1,0,0}A}\ar@{-}[dl]\ar@{-}[ddl]\ar@{-}[dddl]\ar@{-}[% ddddl]\ar@{-}[rrrdd]\ar@{-}[rrrddd]&{\color[rgb]{1,0,0}B}\ar@{-}[dll]\ar@{-}[% ddll]\ar@{-}[dddll]\ar@{-}[ddddll]\ar@{-}[rrdd]\ar@{-}[rrddd]&{\color[rgb]{% 1,0,0}C}\ar@{-}[dlll]\ar@{-}[ddlll]\ar@{-}[dddlll]\ar@{-}[ddddlll]\ar@{-}[rdd]% \ar@{-}[rddd]&\\ {\color[rgb]{0,0,1}D}\ar@{-}[rrrrd]\ar@{-}[rrrrdd]&&&&\\ {\color[rgb]{0,0,1}E}\ar@{-}[rrrr]\ar@{-}[rrrrd]&&&&{\color[rgb]{0,1,0}H}\\ {\color[rgb]{0,0,1}F}\ar@{-}[rrrru]\ar@{-}[rrrr]&&&&{\color[rgb]{0,1,0}I}\\ {\color[rgb]{0,0,1}G}\ar@{-}[rrrruu]\ar@{-}[rrrru]&&&&}

Title	complete k-partite graph
Canonical name	CompleteKpartiteGraph
Date of creation	2013-03-22 12:17:18
Last modified on	2013-03-22 12:17:18
Owner	mps (409)
Last modified by	mps (409)
Numerical id	8
Author	mps (409)
Entry type	Definition
Classification	msc 05C15
Synonym	complete $k$ -partite graph