networkx.generators.classic.turan_graph

turan_graph(n, r)[source]

Return the Turan Graph

The Turan Graph is a complete multipartite graph on \(n\) vertices with \(r\) disjoint subsets. It is the graph with the edges for any graph with \(n\) vertices and \(r\) disjoint subsets.

Given \(n\) and \(r\), 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.