Turán Graph

Author

Eric W. Weisstein
October 10, 2025

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/TuranGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/TuranGraph.html.

©2025 Wolfram Research, Inc. except for portions noted otherwise

Usage

?Turan

?TuranGraph

Construction

MyTuranGraph[n_,k_]:=MakeGraph[Range[n]-1,Mod[#1-#2,k]≠0&,Type->Undirected]

MyTuranGraph[5,4]//RecognizeGraph

GraphData[%24,"StandardNames"]

Figure

GraphicsGrid[Table[Show[StyleGraphs[g=GraphData[gn={"Turan",{n,k}}],{VertexSize->If[VertexCount[g]==1,.03,{"Scaled",.1}]}],PlotLabel->TextCell["("<>StringReplace[StringTake[ToString[GraphData[gn,"NotationRules","Turan"]],{2,-2}]," "->" "]<>")\[Hyphen]Turán graph\n"<>GraphData[gn,"Name"],TextAlignment->Center,PageWidth->700/5]],{n,5},{k,n}],ImageSize->500,Dividers->All,
BaseStyle->InsetBoxOptions->{BaseStyle->Directive[11,Italic,FontFamily->"Times"]},ItemAspectRatio->1,Alignment->Top,ImageSize->700]

Definition

Gross and Yellen, 2006, p. 477

"The Turán graph (Subscript[T, 7,3])"

ShowLabeledGraph[g=Graph[List/@{
{6,7},{6,5},{7,4},{4,5},{1,5},{2,5},{3,5},{3,7},{2,7},{1,7},
{4,1},{4,2},{4,3},{1,6},{2,6},{6,3}
},List/@{{-1,1},{0,1},{1,1},{-1.5,0},{1.5,0},{-.5,-.5},{.5,-.5}}]]

Cases[GraphData[RecognizeGraph[g],"StandardNames"],{"Turan",_}]

TuranGraph[7,3]

RecognizeGraph[FromUnorderedPairs[List@@@EdgeList[TuranGraph[7,3]]]]

GraphData[{"Cone",{4,3}},"StandardNames"]

Chao and Novacky

Chromatic number of D(n,k) == k

Select[{#,Last["Turan"/.GraphData[#,"NotationRules"]],GraphData[#,"ChromaticNumber"]}&/@GraphData["Turan"],#[[2]]≠#[[3]]&]

Grid[{#,Last["Turan"/.GraphData[#,"NotationRules"]],GraphData[#,"ChromaticNumber"]}&/@GraphData["Turan"],Dividers->All,Alignment->{{Left,Decimal,Decimal},Automatic}]

Special cases

TextGrid[turan=Sort[{GraphData[#,"NotationRules","Turan"],#}&/@GraphData["Turan"]],Dividers->All]

Cases[turan,{_,{"Turan",_}}]

Properties

Classes

Intersection@@(GraphData[#,"Classes"]&/@GraphData["Turan"])

FibonacciCube

Entity["Graph",{"Turan",{n,k}}]["FibonacciCube"]

GraphData[#,"NotationRules","Turan"]&/@GraphData[{"Turan","FibonacciCube"}]

LucasCube

Entity["Graph",{"Turan",{n,k}}]["LucasCube"]

GraphData[#,"NotationRules","Turan"]&/@GraphData[{"Turan","LucasCube"}]

Pell

Entity["Graph",{"Turan",{n,k}}]["Pell"]

GraphData[#,"NotationRules","Turan"]&/@GraphData[{"Turan","Pell"}]

Enumeration

Flatten[Table[{{n,k},RecognizeGraph[Turan[n,k]]},{n,7},{k,2,n+1}],1]//Column

Check for larger

Rule@@@(Reverse/@Select[DeleteCases[Flatten[Table[{{n,k},RecognizeGraph[Turan[n,k]]},{n,100},{k,2,n+1}],1],{_,{}}],FreeQ[GraphData[#[[2]],"StandardNames"],"Turan"]&])

Examples

(4,1)

t=Select[GraphData[4],Length[MaximumClique[Graph[#]]]<2&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

Turan[4,1]//RecognizeGraph

(4,2)

t=Select[GraphData[4],Length[MaximumClique[Graph[#]]]<3&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

Turan[4,2]//RecognizeGraph

(4,3)

t=Select[GraphData[4],Length[MaximumClique[Graph[#]]]<4&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t44,First]]

Turan[4,3]//RecognizeGraph

(4,4)

t=Select[GraphData[4],Length[MaximumClique[Graph[#]]]<5&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

Turan[4,4]//RecognizeGraph

(5,1)

t=Select[GraphData[5],Length[MaximumClique[Graph[#]]]<2&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[5,1]]

(5,2)

t=Select[GraphData[5],Length[MaximumClique[Graph[#]]]<3&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[5,2]]

(5,3)

t=Select[GraphData[5],Length[MaximumClique[Graph[#]]]<4&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[5,3]]

(5,4)

t=Select[GraphData[5],Length[MaximumClique[Graph[#]]]<5&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[5,4]]

(5,5)

t=Select[GraphData[5],Length[MaximumClique[Graph[#]]]<6&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[5,5]]

(6,1)

t=Select[GraphData[6],Length[MaximumClique[Graph[#]]]<2&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[6,1]]

(6,2)

t=Select[GraphData[6],Length[MaximumClique[Graph[#]]]<3&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[6,2]]

(6,3)

t=Select[GraphData[6],Length[MaximumClique[Graph[#]]]<4&]

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[6,3]]

(6,4)

t=Select[GraphData[6],Length[MaximumClique[Graph[#]]]<5&];

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[6,4]]

(7,6)

t=Select[GraphData[7],Length[MaximumClique[Graph[#]]]<7&];

Reverse[SortBy[GraphData[#,{"M","#"}]&/@t,First]]

RecognizeGraph[Turan[7,6]]

Discrepancy

A193331

l1=Import["/Users/eww/b193331.txt","Table"]

i=0;
l2=Flatten[Table[{++i,Floor[(k-1) n^2/(2k)]},{n,100},{k,n}],1]

l1===l2

Floor[(k-1) n^2/(2k)/.{n->19,k->13}]

Floor[(k+1) n^2/(2(k+1))/.{n->19,k->13}]

EdgeCount[TuranGraph[n,k]/.{n->19,k->13}]

i=0;
l3=Flatten[Table[{++i,n^2-(Mod[n,k])*(Ceiling[n/k])^2-(k-Mod[n,k])*(Floor[n/k])^2},{n,100},{k,n}],1]

l3==l1

i=0;
l4=Flatten[Table[{++i,EdgeCount[TuranGraph[n,k]]},{n,100},{k,n}],1];//Timing

l3==l4

l4==l2

Select[Transpose[{l3,l4}],Unequal@@#&]

Select[Transpose[{l1,l4}],Unequal@@#&]

GraphData

GraphDataClassString

GraphDataClassString["Turan"]

GraphDataClassString[Intersection@@(GraphData[#,"Classes"]&/@(Complement@@GraphData/@{"Turan","Empty"}))]