turan_graph¶
-
turan_graph
(n, r)[source]¶ Return the Turan Graph
The Turan Graph is a complete multipartite graph on
n
vertices withr
disjoint subsets. It is the graph with the edges for any graph withn
vertices andr
disjoint subsets.Given
n
andr
, we generate a complete multipartite graph with \(r-(n \mod r)\) partitions of size \(n/r\), rounded down, and \(n \mod r\) partitions of size \(n/r+1\), rounded down.Parameters: - n (int) – The number of vertices.
- r (int) – The number of partitions. Must be less than or equal to n.
Notes
Must satisfy \(1 <= r <= n\). The graph has \((r-1)(n^2)/(2r)\) edges, rounded down.