TuranGraph

The complete r-partite graph on n vertices with parts as equal in size as possible.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageTuranGraph✓↗

TuranGraph(n, r)n vertices split into r parts (sizes differ by at most 1), every pair in DIFFERENT parts joined.

SageMathenumeratio_graph(graphs.TuranGraph(n, r))

Typed signatures

Type	Package	Applies
(integer, integer) -> value	combinatorics	always

Domain: Collections

Details

• The extremal K_(r+1)-free graph on n vertices with the most edges (Turán's theorem). r = n gives CompleteGraph(n); r = 1 gives the empty graph on n vertices.
• Vertex-to-part assignment order (which vertices land in the larger parts) is a labelling choice, kernel-unverified against Wolfram's own.

Examples

Basic #

live ↗

In$\mathrm{EdgeCount}(\mathrm{TuranGraph}(6, 3))$Out$12$

Scope #

A complete tripartite graph on five vertices with parts as equal as possible

live ↗

In$\mathrm{TuranGraph}(5, 3)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(2, 5), \mathrm{UndirectedEdge}(3, 5), \mathrm{UndirectedEdge}(4, 5)\bigr\rbrack)$

Applications #

$T(4,2)$ is the $4$-cycle $K_{2,2}$, and $T(6,3)$ is $K_{2,2,2}$, the octahedron

live ↗

In$\bigl\lbrack\mathrm{TuranGraph}(4, 2), \mathrm{TuranGraph}(6, 3)\bigr\rbrack$Out$\bigl\lbrack\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(2, 4)\bigr\rbrack), \mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(1, 6), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(2, 5), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(3, 5), \mathrm{UndirectedEdge}(3, 6), \mathrm{UndirectedEdge}(4, 5), \mathrm{UndirectedEdge}(4, 6)\bigr\rbrack)\bigr\rbrack$

Eccentricities on the five vertices; the last vertex, in the small part, is adjacent to all others

live ↗

In$\mathrm{Map}(\operatorname{\_1}↦\mathrm{VertexEccentricity}(\mathrm{TuranGraph}(5, 3), \operatorname{\_1}), \mathrm{VertexList}(\mathrm{CycleGraph}(5)))$Out$\bigl\lbrack2, 2, 2, 2, 1\bigr\rbrack$

Properties #

Two parts of sizes $4$ and $3$: the complete bipartite graph $K_{4,3}$

live ↗

In$\mathrm{TuranGraph}(7, 2)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(1, 6), \mathrm{UndirectedEdge}(1, 7), \mathrm{UndirectedEdge}(2, 5), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(2, 7), \mathrm{UndirectedEdge}(3, 5), \mathrm{UndirectedEdge}(3, 6), \mathrm{UndirectedEdge}(3, 7), \mathrm{UndirectedEdge}(4, 5), \mathrm{UndirectedEdge}(4, 6), \mathrm{UndirectedEdge}(4, 7)\bigr\rbrack)$

About

Examples	5
Checked against	Wolfram Language 5 agreeSageMath 1 agree3 differ
Crosswalk	Wolfram LanguageSageMath

Implementation

mappedsagepackages/oracle/src/mappings.ts

See also: CompleteGraph