Graph Triameter

Author

Eric W. Weisstein
February 24, 2023

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

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

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

Parametrized familes

AlternatingGroup

seq=Table[GraphData[{"AlternatingGroupGraph",n},"Triameter"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"Triameter"],{n,3,10}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Triameter"],{n,15}]

Antiprism

Entity["Graph",{"Antiprism",n}]["Triameter"]

seq=Table[GraphData[{"Antiprism",n},"Triameter"],{n,3,25}]

FindSequenceFunction[seq,n-2]

Apollonian

Looks like A047244

seq=Table[GraphData[{"Apollonian",n},"Triameter"],{n,6}]

Do[Print[{{"Apollonian",n},{Length[set=GraphTriameter[ApollonianGraph[n]]],set}//Timing}],{n,9}]

seq={3,6,8,9,12,14,15};

FindGeneratingFunction[seq,x]

FindSequenceFunction[DeleteMissing@seq,n]

seq={0,2,3,6,8,9,12,14,15,18,20,21,24,26,27,30,32,33,36,38,39,42,44,45,48,50,51,54,56,57,60,62,63,66,68,69,72,74,75,78,80,81,84,86,87,90,92,93,96,98,99,102,104,105,108,110,111,114,116,117,120,122,123};

FindSequenceFunction[seq,n-1]

FindLinearRecurrence[seq]

LinearRecurrence[{1,0,1,-1},{2,3,6,8},{0,20}]

gf=FindGeneratingFunction[seq,x]

CoefficientList[Series[((x (2+x+3 (x^2)))/((((-1+x))^2) (1+x+(x^2)))),{x,0,20}],x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n∈Integers]

Table[(6 n+Cos[((2 n π)/3)]+(Sqrt[3]) Sin[((2 n π)/3)]-1)/3,{n,0,20}]

Table[(6*n-7-2*Cos[2*n*Pi/3])/3,{n,20}]

FullSimplify[SeriesCoefficient[x gf,{x,0,n}],n∈Integers&&n>0]

Table[(1/3) (-7+6 n-2 Cos[((2 n π)/3)]),{n,0,20}]

Barbell

seq=Table[GraphData[{"Barbell",n},"Triameter"],{n,3,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Triameter"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"Triameter"],{n,10}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"Triameter"],{n,6}]

(seq=Table[GraphTriameter[BruhatGraph[n]],{n,3,7}])//Timing

FindSequenceFunction[seq,n-2]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"Triameter"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["Triameter"]

seq=Table[GraphData[{"Complete",n},"Triameter"],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["Triameter"]

Table[GraphTriameter[System`CompleteGraph[{m,n}]],{n,10},{m,n}]//Column

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["Triameter"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Triameter"],{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Triameter"]

Table[GraphData[{"CompleteTripartite",{k,m,n}},"Triameter"],{n,5},{m,n},{k,m}]//Column

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Triameter"],
Piecewise[{{3,k==m==n==1},{4,Max[k,m,n]==2}},6]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["Triameter"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"Triameter"],{n,10}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"Triameter"],{n,2,10}]

FindSequenceFunction[seq,n-1]

Crown

seq=Table[GraphData[{"Crown",n},"Triameter"],{n,3,20}]

CubeConnectedCycle

A302390

Entity["Graph",{"CubeConnectedCycle",n}]["Triameter"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"Triameter"],{n,3,8}]

FindGeneratingFunction[DeleteMissing@seq,x]

Cycle

Entity["Graph",{"Cycle",n}]["Triameter"]

Table[GraphData[{"Cycle",n},"Triameter"],{n,3,12}]

seq=Table[GraphTriameter[CycleGraph[n]],{n,3,20}]

FindSequenceFunction[seq,n-2]

DiagonalIntersection

A302340

seq=Table[GraphData[{"DiagonalIntersection",n},"Triameter"],{n,3,14}]

Do[Print[{{"FoldedCube",n},GraphTriameter[FoldedCubeGraph[n]]//Timing}],{n,2,15}]

seq={3,4,6,10,14,15,24,25,36,30,52,44,70,59,91,56};

FindGeneratingFunction[seq,x]//Head//Timing

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"Triameter"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["Triameter"]

Table[GraphData[{"Empty",n},"Triameter"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"Triameter"],{n,15}]

FindSequenceFunction[Rest@seq,n-1]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"Triameter"],{n,10}]

FoldedCube

Appears to match A187326

Table[GraphData[{"FoldedCube",n},"Triameter"],{n,2,10}]

Do[Print[{{"FoldedCube",n},GraphTriameter[FoldedCubeGraph[n]]//Timing}],{n,2,15}]

seq={$Failed,3,6,6,8,9,12,12,14,15};

FindGeneratingFunction[Rest@seq,x]//Head//Timing

Table[Floor[n/4]+Floor[n/2]+Floor[3n/4],{n,0,20}]

Gear

seq=Table[GraphData[{"Gear",n},"Triameter"],{n,3,20}]

Grid m×n

Entity["Graph",{"Cycle",n}]["Triameter"]

Table[GraphData[{"Grid",{m,n}},"Triameter"],{n,10},{m,n}]//Column

Table[Piecewise[{{Missing["NotApplicable"],m n==1||m n==2}},2(m+n-2)],{n,10},{m,n}]//Column

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["Triameter"]

seq=Table[GraphData[{"Grid",{n,n}},"Triameter"],{n,20}]

FindSequenceFunction[DeleteMissing@Rest@seq,n-1]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["Triameter"]

Table[GraphData[{"Grid",{k,m,n}},"Triameter"],{n,5},{m,n},{k,m}]//Column

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Triameter"],
Piecewise[{{Missing["NotApplicable"],k m n==1||k m n==2}},2(k+m+n-3)]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["Triameter"]

seq=Table[GraphData[{"Grid",{n,n,n}},"Triameter"],{n,10}]

FindSequenceFunction[DeleteMissing@Rest@seq,n-1]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"Triameter"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"Triameter"],{n,5}]

FindSequenceFunction[seq,n]

Helm

seq=Table[GraphData[{"Helm",n},"Triameter"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["Triameter"]

seq=Table[GraphData[{"Hypercube",n},"Triameter"],{n,10}]

Keller

Entity["Graph",{"Keller",n}]["Triameter"]

seq=Table[GraphData[{"Keller",n},"Triameter"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"Triameter"],{n,20}]

FindSequenceFunction[Rest@seq,n-1]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["Triameter"]

Knight n×n

A302341

Entity["Graph",{"Knight",{n,n}}]["Triameter"]

seq=Table[GraphData[{"Knight",{n,n}},"Triameter"],{n,20}]

Do[Print[{{"Knight",{n,n}},GraphTriameter[KnightGraph[n,n]]//Timing}],{n,30}]

FindGeneratingFunction[seq,x]//Head//Timing

seq={12,12,12,12,16,16,18,20,22,22,24,26,28,30,32,32,36,36,38,40,42,42,44,46,48,50,52,52,56,56,58,60,62,62,64,66,68,70,72,72,76,76,78,80,82,82,84,86,88,90,92,92,96,96,98,100,102,102,104,106,108,110,112,112};

FindSequenceFunction[Drop[seq,2],n-2]

RSolve[{-226-20 \[FormalN]+\[FormalY][\[FormalN]]+\[FormalY][1+\[FormalN]]+\[FormalY][2+\[FormalN]]+\[FormalY][3+\[FormalN]]+\[FormalY][4+\[FormalN]]+\[FormalY][5+\[FormalN]]+\[FormalY][6+\[FormalN]]+\[FormalY][7+\[FormalN]]+\[FormalY][8+\[FormalN]]+\[FormalY][9+\[FormalN]]+\[FormalY][10+\[FormalN]]+\[FormalY][11+\[FormalN]]==0,\[FormalY][1]==12,\[FormalY][2]==12,\[FormalY][3]==16,\[FormalY][4]==16,\[FormalY][5]==18,\[FormalY][6]==20,\[FormalY][7]==22,\[FormalY][8]==22,\[FormalY][9]==24,\[FormalY][10]==26,\[FormalY][11]==28},\[FormalY][\[FormalN]],\[FormalN]]

coef=FindLinearRecurrence[Drop[seq,2]]

Length[coef]

Take[Drop[seq,2],Length@coef]

seq2=Join[{12,12},LinearRecurrence[{1,0,0,0,0,0,0,0,0,0,0,1,-1},{12,12,16,16,18,20,22,22,24,26,28,30,32},62]]

seq2==seq

gf=(x^4) FindGeneratingFunction[seq2,x,ValidationLength->10]

InputForm[gf]

CoefficientList[Series[((2 (6+2 (x^4)+(x^6)+(x^7)+(x^8)+(x^10)+(x^11)-5 (x^12)+(x^13)+(x^14)))/((((-1+x))^2) (1+x+(x^2)+(x^3)+(x^4)+(x^5)+(x^6)+(x^7)+(x^8)+(x^9)+(x^10)+(x^11)))),{x,0,63}],x]==seq

Series[gf,{x,0,20}]

soln=Simplify[SeriesCoefficient[((2 (x^4) (6+2 (x^4)+(x^6)+(x^7)+(x^8)+(x^10)+(x^11)-5 (x^12)+(x^13)+(x^14)))/((((-1+x))^2) (1+x+(x^2)+(x^3)+(x^4)+(x^5)+(x^6)+(x^7)+(x^8)+(x^9)+(x^10)+(x^11)))),{x,0,n}],n>5&&n∈Integers]

Table[soln,{n,6,67}]//FullSimplify

soln2=FullSimplify[soln,n∈Integers]

Table[FullSimplify[soln2,Mod[n,6]==k&&Element[n,Integers]],{k,0,5}]

Join[{12,12},Table[(1/6) (8+2 (((-1))^n)+10 n+Cos[((n π)/3)] (1-2 (((-1))^n) Cos[((n π)/2)])+Cos[((2 n π)/3)]-(Sqrt[3]) Sin[((n π)/3)]+2 Cos[((n π)/2)] (1+(((-1))^n) (Sqrt[3]) Sin[((n π)/3)])-((5 Sin[((2 n π)/3)])/(Sqrt[3]))),{n,6,67}]]==seq

a[n_]:=1/6 (8+2 (-1)^n+10 n+Cos[n Pi/3] (1-2 (-1)^n Cos[n Pi/2])+Cos[2 n Pi/3]-Sqrt[3] Sin[n Pi/3]+2 Cos[n Pi/2] (1+(-1)^n Sqrt[3] Sin[n Pi/3])-(5 Sin[2 n Pi/3])/Sqrt[3])

Table[FullSimplify[a[n]-a[n-12k]],{k,10}]

FullSimplify[a[n]-a[n-k],n∈Integers&&Mod[k,12]==0]//Timing

Grid[Table[{k,FullSimplify[a[n]-a[n-k],n∈Integers]},{k,25}],Dividers->All,Alignment->Left]

Ladder

Entity["Graph",{"Ladder",n}]["Triameter"]

seq=Table[GraphData[{"Ladder",n},"Triameter"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"Triameter"],{n,20}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"Triameter"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["Triameter"]

seq=Table[GraphData[{"MoebiusLadder",n},"Triameter"],{n,3,25}]

FindSequenceFunction[Drop[seq,2],n-4]

Mycielski

Entity["Graph",{"Mycielski",n}]["Triameter"]

seq=Table[GraphData[{"Mycielski",n},"Triameter"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["Triameter"]

seq=Table[GraphData[{"Odd",n},"Triameter"],{n,7}]

FindSequenceFunction[DeleteMissing@Rest@seq,n-1]

Pan

seq=Table[GraphData[{"Pan",n},"Triameter"],{n,3,20}]

FindSequenceFunction[seq,n-2]

Path

Entity["Graph",{"Path",n}]["Triameter"]

seq=Table[GraphData[{"Path",n},"Triameter"],{n,20}]

FindSequenceFunction[Drop[seq,2],n-2]//Simplify

Prism

Entity["Graph",{"Prism",n}]["Triameter"]

seq=Table[GraphData[{"Prism",n},"Triameter"],{n,3,25}]

FindSequenceFunction[seq,n-2]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"Triameter"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"Triameter"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"Triameter"],{n,10}]

SierpinskiCarpet

A302507

seq=Table[GraphData[{"SierpinskiCarpet",n},"Triameter"],{n,4}]

FindSequenceFunction[DeleteMissing@seq,n]

seq=Table[4 (-1+(3^n)),{n,0,40}]

FindLinearRecurrence[seq]

LinearRecurrence[{4,-3},{8,32},{0,20}]

gf=FindGeneratingFunction[seq,x]//Factor

InputForm[gf]

CoefficientList[Series[((8 x)/((-1+x) (-1+3 x))),{x,0,20}],x]

SierpinskiSieve

seq=Table[GraphData[{"SierpinskiSieve",n},"Triameter"],{n,5}]

FindSequenceFunction[DeleteMissing@seq,n]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"Triameter"],{n,6}]

FindSequenceFunction[DeleteMissing@seq,n]

Star

Entity["Graph",{"Star",n}]["Triameter"]

Table[GraphData[{"Star",n},"Triameter"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"Triameter"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"Triameter"],{n,3,20}]

FindSequenceFunction[seq,n-2]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"Triameter"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"Triameter"],{n,3,10}]

FindSequenceFunction[seq,n-2]

Transposition

Entity["Graph",{"Transposition",n}]["Triameter"]

seq=Table[GraphData[{"Transposition",n},"Triameter"],{n,6}]

Triangular

seq=Table[GraphData[{"Triangular",n},"Triameter"],{n,2,12}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"Triameter"],{n,0,10}]

FindSequenceFunction[Rest@seq,n]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"Triameter"],{n,20}]

TriangularHoneycombBishop

Table[GraphData[{"TriangularHoneycombBishop",n},"Triameter"],{n,9}]

TriangularHoneycombObtuseKnight

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Triameter"],{n,10}]

TriangularHoneycombQueen

Table[GraphData[{"TriangularHoneycombQueen",n},"Triameter"],{n,10}]

TriangularHoneycombRook

Table[GraphData[{"TriangularHoneycombRook",n},"Triameter"],{n,10}]

Web

seq=Table[GraphData[{"Web",n},"Triameter"],{n,3,20}]

FindSequenceFunction[seq,n-2]

Wheel

Entity["Graph",{"Wheel",n}]["Triameter"]

Table[GraphData[{"Wheel",n},"Triameter"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Triameter"],{n,2,10}]