complete k-partite graph

A complete k-partite graph is a maximal k-partite graph. In other words, a graph is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath k-partite provided that its vertex set admits a partitionMathworldPlanetmathPlanetmath V=V1Vk such that for any uVi and vVj, uv is an edge if and only if ij.

For any tuple (a1,,ak), there is up to graph isomorphismMathworldPlanetmath a single complete k-partite graph with maximal stable sets V1,,Vk such that for each i, there are exactly ai vertices in Vi. This graph is denoted by Ka1,,ak.

Below we display the 3-partite complete graph K2,3,4:

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