From Surf Wiki (app.surf) — the open knowledge base

Turán graph

Quality 0.00 · 0 views · Updated 1 month ago

The Turán graph, denoted by T ( n , r ) {\displaystyle T(n,r)} , is a complete multipartite graph; it is formed by partitioning a set of n {\displaystyle n} vertices into r {\displaystyle r} subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where q {\displaystyle q} and s {\displaystyle s} are the quotient and remainder of dividing n {\displaystyle n} by r {\displaystyle r} (so n = q r + s {\displaystyle n=qr+s} ), the graph is of the form K q + 1 , q + 1 , … , q , q {\displaystyle K_{q+1,q+1,\ldots ,q,q}} , and the number of edges is