Bipartite graphs and partitions
In a bipartite graph, it is possible to partition the set of vertices into two sets such that none of the vertices in either set are adjacent to one another.
|Here are some examples:|
An n-partite graph is defined similarly, with the vertices partitioned into n sets or partitions.
A complete n-partite graph is a graph where every vertex in each partition is connected to all the vertices of the graph which are not contained in that partition A complete n- partite graph is denoted K(p1, p2, . . . , pn) where pn denotes the number of vertices in each partition. Thus K(3, 3) is a complete bipartite graph with 3 vertices in each partition and K(3, 4, 5) is a complete tripartite graph with partitions of 3, 4, and 5 vertices.
|K(3, 3)||K(4, 2)||K(2, 3, 2)|
Copyright © 1999-2000 SciMathMN