|
|
|
|
|
Turan GraphThe Turan graph T(n,r) is the complete r-partite graph with n vertices whose partite sets differ in size at most 1. Think about this graph as a process: First you take place for the r parts. And then, you allocate the vertices to this parts in equal size (or almost equal size). The size of each part is floor or ceil of n/r. Then you add all the edges between each pair of vertices which belongs to a different part. So the total number of edges is -
with n = rt. Clearly, the Turan graph T(n,r) does not contain a clique of size r+1. This is the best possible (with respect to the number of edges) among all graphs with n vertices (see Turan's theorem). See also * Extremal graph theory
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|