turan_graph#

turan_graph(n, r)[source]#

Return the Turan Graph

The Turan Graph is a complete multipartite graph on $n$ nodes with $r$ disjoint subsets. That is, edges connect each node to every node not in its subset.

Given $n$ and $r$, we create a complete multipartite graph with $r-(n\mathrm{mod}r)$ partitions of size $n/r$, rounded down, and $n\mathrm{mod}r$ partitions of size $n/r+1$, rounded down.

(Source code, png)

Parameters:

nint

The number of nodes.

rint

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.

---

Additional backends implement this function

cugraph : GPU-accelerated backend.