Graph Diameter

Author

Eric W. Weisstein
June 11, 2019

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

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

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

Counts

SetDirectory[FileNameJoin[{$GraphDataDirectory,"Nodes"}]];

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Get/@FileNames["*.m","Diameter"]))//Column

Tally[Sort[#]][[All,1]]&/@values//Column

GraphDiameter[Graph[{1},{}]]

A308618

Rest@Flatten[tallies]

A000088

Total/@tallies

tallies[[All,1]]

Not in OEIS:

Total/@values

Smallest diameter (unique);

Table[Select[GraphData[n],GraphData[#,"Diameter"]==1&],{n,2,10}]//Column

Largest diameter (unique)

Table[Select[GraphData[n],GraphData[#,"Diameter"]==n-1&],{n,2,10}]//Column

Select[GraphData[4],GraphData[#,"Diameter"]==2&]

GraphData[#,"Diameter"]&/@%

Figure

m

Show[GraphicsArray[ShowGraph/@m /.PointSize[_]:>PointSize[.05]]]

Diameter/@m

Parametrized families

Andrasfai

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

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Diameter"],{n,10}]

Antiprism

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

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

FindSequenceFunction[seq,n-2]//FullSimplify

Apollonian

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

Barbell

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

Bishop n×n

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

BlackBishop n×n

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

Book

seq=Table[GraphData[{"Book",n},"Diameter"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"Diameter"],{n,10}]

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
Piecewise[{{1,m==n==1}},2],
GraphData[{"CompleteBipartite",{m,n}},"Diameter"]
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

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

FindSequenceFunction[Rest@seq,n-3]

Cycle

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

seq=Table[GraphData[{"Cycle",n},"Diameter"],{n,3,20}]

DiagonalIntersection

A300526

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

Empty

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

seq=Table[GraphData[{"Empty",n},"Diameter"],{n,30}]

FibonacciCube

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

Fiveleaper n×n

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

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"Diameter"],{n,2,10}]

Gear

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

GeneralizedPetersen

Grid 3×n

seq=Table[GraphData[{"Grid",Sort[{3,n}]},"Diameter"],{n,10}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["Diameter"]

Grid n×n

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

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

Grid k×m×n

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

Grid n×n×n

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

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

HalvedCube

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

Hanoi

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

FindSequenceFunction[seq,n]

Helm

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

Hypercube

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

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

Keller

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

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

King m×n

Table[GraphData[{"King",{m,n}},"Diameter"],{n,10},{m,n}]//Column

King 2×n

seq=Table[GraphData[{"King",Sort[{2,n}]},"Diameter"],{n,10}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"Diameter"],{n,10}]

Knight m×n

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

Table[GraphData[{"Knight",{m,n}},"Diameter"],{n,10},{m,n}]//Column

Knight n×n

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

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

Ladder

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

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

LadderRung

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

MengerSponge

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

(seq=Table[GraphDiameter[MengerSpongeGraph[n]],{n,4}])//Timing

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Pan

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

Path

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

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

Prism

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

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

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"Diameter"],{n,10}]

Rook m×n

Table[GraphData[{"Rook",{m,n}},"Diameter"],{n,10},{m,n}]//Column

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"Diameter"],{n,10}]

RookComplement n×n

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

SierpinskiCarpet

A100774

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

Do[
Print[{{"SierpinskiCarpet",n},GraphDiameter[SierpinskiCarpetGraph[n]]//Timing}],{n,5}]

seq={4,16,52,160,484};

FindSequenceFunction[seq,n]

Table[2 (-1+(3^n)),{n,0,20}]

seq=2(3^Range[0,20]-1)

FindLinearRecurrence[seq]

LinearRecurrence[{4,-3},{4,16},{0,20}]

gf=FindGeneratingFunction[seq,x]

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

SierpinskiSieve

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

SierpinskiTetrahedron

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

Star

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

seq=Table[GraphData[{"Star",n},"Diameter"],{n,25}]

Sun

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

Sunlet

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

Tetrahedral

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

Transposition

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

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

Triangular

seq=Table[GraphData[{"Triangular",n},"Diameter"],{n,2,20}]

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"Diameter"],{n,9}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Diameter"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"Diameter"],{n,10}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"Diameter"],{n,10}]

Web

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

Wheel

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

seq=Table[GraphData[{"Wheel",n},"Diameter"],{n,4,20}]

WhiteBishop n×n

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

Checks

Combinatorica

DeleteCases[{GraphData[#,"Diameter"],Diameter[Graph[#]]}&/@GraphData[;;9],{x_,x_}]//Timing

Built-in GraphDiameter

DeleteCases[{GraphData[#,"Diameter"],GraphDiameter[GraphData[#]]}&/@GraphData[;;9],{x_,x_}]//Timing

DeleteCases[{GraphData[#,"Diameter"],GraphDiameter[GraphData[#]]}&/@GraphData[;;12],{x_,x_}]//Timing