Graph Bandwidth

Author

Eric W. Weisstein
February 9, 2024

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

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

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

Counts

Tally[Sort[#]]&/@(values=Table[Bandwidth/@Graphs[n],{n,7}])//Column

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

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

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

A294223

Flatten[tallies]

A000088

Total/@tallies

A000041

tallies[[All,1]]

1 for n≠2

tallies[[All,-1]]

Not in OEIS:

Drop[tallies,2][[All,2]]

Not in OEIS:

Drop[tallies,2][[All,-2]]

Length/@tallies

Not in OEIS:

Total/@values

Inequalities

bw(G) ≥ χ(G)-1

Select[GraphData["Connected",;;14],!(GraphData[#,"Bandwidth"]>=GraphData[#,"ChromaticNumber"]-1)&]

(Ceiling[((n-1)/(d(G)))])≤bw(G)≤n-d(G)

Select[GraphData["Connected",2;;14],!(Ceiling[(GraphData[#,"V"]-1)/GraphData[#,"Diameter"]]<=GraphData[#,"Bandwidth"]<=GraphData[#,"V"]-GraphData[#,"Diameter"])&]

all=Select[GraphData["Bandwidth","Defined"],GraphData[#,"V"]>1&&Ceiling[(GraphData[#,"V"]-1)/GraphData[#,"Diameter"]]==GraphData[#,"Bandwidth"]&];

Select[all,GraphData[#,"Disconnected"]&]

Graphs with minimal bw:

A308568

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes"]

Table[
bw=Import[FileNameJoin[{"Bandwidth","Bandwidth_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[ConnectedGraphIndices[n]]];
d=Import[FileNameJoin[{"Diameter","Diameter_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]];
Total[Boole[Ceiling[(n-1)/#1]==#2&@@@Transpose[{d,bw}]]],
{n,2,9}]

FindSequenceFunction[%,n-1]

FindGeneratingFunction[%%,x]

Table[Length[Select[GraphData["Connected",n],Ceiling[(GraphData[#,"V"]-1)/GraphData[#,"Diameter"]]==GraphData[#,"Bandwidth"]&]],{n,2,7}]

Table[Length[Select[GraphData["Connected",n],Ceiling[(GraphData[#,"V"]-1)/GraphData[#,"Diameter"]]<GraphData[#,"Bandwidth"]&]],{n,2,7}]

TextGrid[Table[{n,Length[min=Select[GraphData[n],Ceiling[(GraphData[#,"V"]-1)/GraphData[#,"Diameter"]]==GraphData[#,"Bandwidth"]&]],min},{n,2,6}],Dividers->All,Alignment->{{{Decimal},Left}}]

TextGrid[Table[{n,Length[min=Select[GraphData["Connected",n],Ceiling[(GraphData[#,"V"]-1)/GraphData[#,"Diameter"]]!=GraphData[#,"Bandwidth"]&]],min},{n,2,6}],Dividers->All,Alignment->{{{Decimal},Left}}]

TextGrid[Table[{n,Length[min=Select[GraphData["Connected",n],Ceiling[(GraphData[#,"V"]-1)/GraphData[#,"Diameter"]]!=GraphData[#,"Bandwidth"]&]],GraphData[#,"Notation"]&/@min},{n,2,6}],Dividers->All,Alignment->{{{Decimal},Left}}]//TraditionalForm

GraphData[{5,31}]

GraphData[{5,31},"StandardNames"]

tw(G) ≤ pw(G) ≤ b(G)

Tallies by node count

Graphs[#,Format->"AdjacencyMatrix"]&/@Range[7];//AbsoluteTiming

bws=Table[Tally[Sort[Bandwidth/@AdjacencyGraph/@Graphs[n,Format->"AdjacencyMatrix"]]],{n,7}]

#[[All,1]]&/@bws

#[[All,2]]&/@bws

Plus@@@(Times@@@#&/@bws)

{1,2,5,18,71,402,3183}-1

Cf. A086828
0, 1, 1, 7, 11, 46, 112, 
Number of networks with bandwidth n.

which I don’t understand

Parametrized family table

GraphDataCountTable["Bandwidth",Join[
{"Antiprism"->010709,"Apollonian"->363055,"Bishop"->002620,"BlackBishop"->002620,"Book"->066530,"King"->065475,"Mycielski"->083329,"Queen"->363056,"Rook"->000096,"WhiteBishop"->002620},
Thread[{"Barbell"}->27], (* 1, 2, 3, ... *)
Thread[{"Empty"}->000012], (* 1s *)
Thread[{"Cycle"}->007395], (* 2s *)
Thread[{"Complete","CycleComplement"}->028310],(* 1, 1, 2, 3, ... *)
Thread[{"Andrasfai","CocktailParty"}->004275]
]]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"Bandwidth"],{n,10}]

Do[
Print[{gn=GraphData[{"Alkane",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,10}]

Andrasfai

A032766

seq=Table[GraphData[{"Andrasfai",n},"Bandwidth"],{n,20}]

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

Do[
Print[{gn=GraphData[{"Andrasfai",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,10}]

Antelope n×n

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

Do[
Print[{gn=GraphData[{"Antelope",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

Antiprism

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

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

Apollonian

A363055

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

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

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

Do[
Print[{gn=GraphData[{"Apollonian",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,6}]

Barbell

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

Bishop n×n

A002620

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

Table[Piecewise[{{1,n==1}},Floor[n^2/4]],{n,10}]

Do[
Print[{gn=GraphData[{"Bishop",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,10}]

BlackBishop n×n

A002620

Inferred for n > 14:

seq=Table[GraphData[{"BlackBishop",{n,n}},"Bandwidth"],{n,20}]

Table[Piecewise[{{1,n==1}},Floor[n^2/4]],{n,20}]

Do[
Print[{gn=GraphData[{"BlackBishop",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,14}]

Book

A066530

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

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n∈Integers]

Table[(1/8) (7-(((-1))^n)+6 n+2 Cos[((n π)/2)]+2 Sin[((n π)/2)]),{n,50}]

Table[Floor[(3n+5)/4],{n,50}]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

Do[
Print[{gn=GraphData[{"Book",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"Bandwidth"],{n,20}]

Do[
Print[{gn=GraphData[{"Camel",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

Centipede

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

Do[
Print[{gn=GraphData[{"Centipede",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,10}]

CocktailParty

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

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

Complete

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

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

CompleteBipartite m×n

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

DeleteCases[Block[{m,n},Sort[
{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],
Floor[(1/2) (-1+Max[m,n])]+Min[m,n],
GraphData[#,"Bandwidth"]
}&/@GraphData["CompleteBipartite"]]],{_,x_,x_}]

CompleteBipartite n×n

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

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

Table[Floor[(1/2) (3n-1)],{n,20}]

CompleteTripartite k×m×n

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

Table[{k,m,n},{k,5},{m,k},{n,m}]

data=DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Bandwidth"],
k+m+n
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

DeleteCases[{#,#3-#2}&@@@data,{_,0}]

CompleteTripartite n×n×n

A047211

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

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Simplify[SeriesCoefficient[gf,{x,0,n}],n>0]

Table[(10 n-3-(((-1))^n))/4,{n,12}]

Do[
Print[{gn=GraphData[{"CompleteTripartite",{n,n,n}},"#"],Bandwidth[CompleteGraph[{n,n,n}]]//AbsoluteTiming}],
{n,12}]

CrossedPrism

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

Do[
Print[{gn=GraphData[{"CrossedPrism",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,4,20,2}]

Crown

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

gf=(x^3)FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>3]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>4]

Do[
Print[{gn=GraphData[{"Crown",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3,20}]

CubeConnectedCycle

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

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

Cycle

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

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

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"Bandwidth"],{n,3,20}]

Do[
Print[{gn=GraphData[{"CycleComplement",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3,20}]

DiagonalIntersection

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

Do[
Print[{gn=GraphData[{"DiagonalIntersection",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3,14}]

...next one takes a while...

Dipyramid

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

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"Bandwidth"],{n,3,20}]

Do[
Print[{gn=GraphData[{"DoubleCone",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],{n,3,20}]

Empty

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

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

FibonacciCube

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

Do[
Print[{gn=GraphData[{"FibonacciCube",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,15}]

Fiveleaper n×n

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

Do[
Print[{gn=GraphData[{"Fiveleaper",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,15}]

Flower

seq=Table[GraphData[{"Flower",n},"Bandwidth"],{n,5,20}]

Do[
Print[{gn=GraphData[{"Flower",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,5,20}]

FoldedCube

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

Do[
Print[{gn=GraphData[{"FoldedCube",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,2,20}]

Gear

Inferred for n > 14:

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

Do[
Print[{gn=GraphData[{"Gear",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3,20}]

GeneralizedPetersen

Sort[{"GeneralizedPetersen"/.GraphData[#,"NotationRules"],GraphData[#,"Bandwidth"]}&/@GraphData["GeneralizedPetersen"]]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"Bandwidth"],{n,20}]

Goldberg

Inferred for n==10:

seq=Table[GraphData[{"Goldberg",n},"Bandwidth"],{n,3,20}]

Do[
Print[{gn=GraphData[{"Goldberg",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3,20}]

Grid 3×n

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

Grid m×n

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

DeleteCases[Block[{m,n},Sort[{
{m,n}="Grid"/.GraphData[#,"NotationRules"],
GraphData[#,"Bandwidth"],
Min[m,n]}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==2&]]],{_,x_,x_}]

Grid n×n

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

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

Grid k×m×n

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

Grid n×n×n

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

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

Do[
Print[{gn=GraphData[{"Grid",{n,n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,10}]

HalvedCube

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

Do[
Print[{gn=GraphData[{"HalvedCube",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,10}]

Hanoi

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

Do[
Print[{gn=GraphData[{"Hanoi",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,5}]

Helm

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

Do[
Print[{gn=GraphData[{"Helm",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3,20}]

Hypercube

A036256

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

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

Table[Sum[Binomial[k,Floor[k/2]],{k,0,n}],{n,0,20}]

V9

Sum[Binomial[k,Floor[k/2]],{k,0,n-1}]

s1=Sum[Binomial[k,Floor[k/2]],{k,0,n-1,2}]

s2=Sum[Binomial[k,Floor[k/2]],{k,1,n-1,2}]

FullSimplify[s1+s2,n∈Integers&&n>0]

Refine[s1+s2,n∈Integers&&n>0]

Table[s1+s2,{n,20}]//FullSimplify

Table[Piecewise[{{(1/2)(-1-I Sqrt[3]-(3Gamma[3+n]Hypergeometric2F1Regularized[1,(3+n)/2,(4+n)/2,4])/Gamma[2+n/2]),Mod[n,2]==0},{((-1-I*Sqrt[3])Gamma[(1+n)/2]-4n!(Hypergeometric2F1Regularized[1,(2+n)/2,(3+n)/2,4]+(2+n)Hypergeometric2F1Regularized[1,(4+n)/2,(5+n)/2,4]))/(2*Gamma[(1+n)/2]),Mod[n,2]==1}}],{n,0,20}]//Expand

Keller

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

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

Do[
Print[{gn=GraphData[{"Keller",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,5}]

King m×n

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"Bandwidth"],
Piecewise[{{1,Min[m,n]==1}},Min[m,n]+1]
},{n,10},{m,n}],1],{_,x_,x_}]

Inferred for:

Print[{gn={"King",#},{0,Bandwidth[GraphData[gn]]//AbsoluteTiming}}]&/@%[[All,1]]

King 2×n

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

King n×n

A065475

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

Do[
Print[{gn=GraphData[{"King",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

Knight m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"Bandwidth"],
Piecewise[{{1,Min[m,n]<3}},XXX]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

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

Do[
Print[{gn=GraphData[{"Knight",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

Ladder

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

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

LadderRung

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

MengerSponge

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

Do[
Print[{gn=GraphData[{"MengerSponge",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3}]

MoebiusLadder

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

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

Mycielski

A083329

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

Inferred for n > 9:

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

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

SeriesCoefficient[gf,{x,0,n}]//FullSimplify

Table[Piecewise[{{1,n==1||n==2}},3 (2^(n-3))-1],{n,11}]

Do[
Print[{gn=GraphData[{"Mycielski",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,11}]

Odd

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

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

Do[
Print[{gn=GraphData[{"Odd",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,7}]

Pan

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

Path

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

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

Prism

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

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

Queen n×n

A363056

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

Do[
Print[{gn=GraphData[{"Queen",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

Rook m×n

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

Rook n×n

A000096

Inferred for n > 6:

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

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

Table[Piecewise[{{1,n==1}},(n-1)(n+2)/2],{n,20}]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Simplify[SeriesCoefficient[gf,{x,0,n}],n>1]//Factor

Do[
Print[{gn=GraphData[{"Rook",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

RookComplement n×n

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

FindSequenceFunction[seq,n]//Head//Timing

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

Do[
Print[{gn=GraphData[{"RookComplement",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,10}]

SierpinskiCarpet

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

Do[
Print[{gn=GraphData[{"SierpinskiCarpet",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,4}]

SierpinskiSieve

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

Do[
Print[{gn=GraphData[{"SierpinskiSieve",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,5}]

SierpinskiTetrahedron

Possibly A000051

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

Table[(2^n)+1,{n,6}]

Do[
Print[{gn=GraphData[{"SierpinskiTetrahedron",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,6}]

StackedBook m×n

Table[GraphData[{"StackedBook",{m,n}},"Bandwidth"],{m,10},{n,10}]//Column//TraditionalForm

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"Bandwidth"],{n,10}]

Do[
Print[{gn=GraphData[{"StackedBook",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,10}]

Star

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

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

Sun

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

FindSequenceFunction[Rest@seq,n-3]//Factor

Sunlet

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

Do[
Print[{gn=GraphData[{"Sunlet",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3,20}]

Tetrahedral

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

Do[
Print[{gn=GraphData[{"Tetrahedral",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,6,10}]

Transposition

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

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

Do[
Print[{gn=GraphData[{"Transposition",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,6}]

Trapezohedron

seq=Table[GraphData[{"Trapezohedron",n},"Bandwidth"],{n,3,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n-2],n∈Integers]

FullSimplify[FindSequenceFunction[Rest@DeleteMissing@seq,n-3],n∈Integers]

gf=(x^3) FindGeneratingFunction[DeleteMissing@seq,x]

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

Table[Piecewise[{{4,n==3}},(1/8) (9+(((-1))^n)+6 n-2 Cos[((n π)/2)]+2 Sin[((n π)/2)])],{n,3,20}]

Do[
Print[{gn=GraphData[{"Trapezohedron",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3,20}]

Do[
Print[{gn=GraphData[{"Trapezohedron",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,18,20}]

Triangular

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

FindSequenceFunction[DeleteMissing@seq,n-1]//Head//Timing

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

Do[
Print[{gn=GraphData[{"Triangular",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,2,9}]

TriangularGrid

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

TriangularHoneycombAcuteKnight

A004526

Inferred for n > 16:

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

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

SeriesCoefficient[gf,{x,0,n}]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>5]

Table[Piecewise[{{1,n==3},{2,n==5}},Ceiling[n/2]],{n,16}]==Take[seq,16]

Do[
Print[{gn=GraphData[{"TriangularHoneycombAcuteKnight",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

...ran 2 days+...

Do[
Print[{gn=GraphData[{"TriangularHoneycombAcuteKnight",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,15,20}]

TriangularHoneycombBishop

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

Do[
Print[{gn=GraphData[{"TriangularHoneycombBishop",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,9}]

Do[
Print[{{"BlackBishop",{n,n+1}},Bandwidth[TriangularHoneycombBishopGraph[n]]//AbsoluteTiming}],
{n,9,11}]

Table[Floor[Binomial[n,2]/2],{n,11}]

TriangularHoneycombObtuseKnight

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

Do[
Print[{gn=GraphData[{"TriangularHoneycombObtuseKnight",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

TriangularHoneycombQueen

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

Do[
Print[{gn=GraphData[{"TriangularHoneycombAcuteKnight",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,10}]

TriangularHoneycombRook

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

Web

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

Do[
Print[{gn=GraphData[{"Web",n},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,3,20}]

Wheel

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

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

WhiteBishop n×n

A002620

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Bandwidth"],{n,2,20}]

Table[Floor[n^2/4],{n,2,20}]==seq

Do[
Print[{gn=GraphData[{"WhiteBishop",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,2,20}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"Bandwidth"],{n,20}]

Do[
Print[{gn=GraphData[{"Zebra",{n,n}},"#"],Bandwidth[GraphData[gn]]//AbsoluteTiming}],
{n,20}]

Algorithms

FastSerial

(bad=DeleteCases[
Monitor[{
gn=#,
GraphData[#,"Bandwidth"],
Bandwidth[GraphData[#],Method->"FastSerial"]
}&/@GraphData[;;6],
gn],
{_,x_,x_}])//Timing

Sage

(bad=DeleteCases[
Monitor[{
gn=#,
GraphData[#,"Bandwidth"],
Bandwidth[GraphData[#],Method->"Sage"]
}&/@GraphData[;;4],
gn],
{_,x_,x_}])//AbsoluteTiming

Bandwidth[CompleteGraph[4],Method->"Sage",Debug->True]//AbsoluteTiming

Intersection[GraphData["Bandwidth","Missing"],GraphData[15]]

Print[{#,Bandwidth[GraphData[#],Method->"Sage"]//AbsoluteTiming}]&/@%16

Algorithm

Comparison n=1-5

bw1=Bandwidth[GraphData[#],Method->"Serial"]&/@GraphData["Connected",;;5];//Timing

bw2=Bandwidth[GraphData[#],Method->"FastSerial"]&/@GraphData["Connected",;;5];//Timing

bw3=Bandwidth[GraphData[#],Method->"NextPermutation",CompilationTarget->"WVM"]&/@GraphData["Connected",;;5];//Timing

bw4=Bandwidth[GraphData[#],Method->"NextPermutation",CompilationTarget->"C"]&/@GraphData["Connected",;;5];//Timing

bw1==bw2==bw3==bw4

Comparison n=6

bw1=Bandwidth[GraphData[#],Method->"Serial"]&/@GraphData["Connected",6];//Timing

bw2=Bandwidth[GraphData[#],Method->"FastSerial"]&/@GraphData["Connected",6];//Timing

bw3=Bandwidth[GraphData[#],Method->"NextPermutation",CompilationTarget->"WVM"]&/@GraphData["Connected",6];//Timing

bw4=Bandwidth[GraphData[#],Method->"NextPermutation",CompilationTarget->"C"]&/@GraphData["Connected",6];//Timing

bw1==bw2==bw3==bw4

Comparison n=7

bw1=Monitor[Bandwidth[GraphData[g=#],Method->"Serial"]&/@GraphData["Connected",7],g];//Timing

bw2=Bandwidth[GraphData[#],Method->"FastSerial"]&/@GraphData["Connected",7];//Timing

test=Monitor[Bandwidth[GraphData[g=#],Method->"NextPermutation"]&/@GraphData["Connected",7],g];//Timing

bw3=Monitor[Bandwidth[GraphData[g=#],Method->"NextPermutation",CompilationTarget->"WVM"]&/@GraphData["Connected",7],g];//Timing

bw4=Monitor[Bandwidth[GraphData[g=#],Method->"NextPermutation",CompilationTarget->"C"]&/@GraphData["Connected",7],g];//Timing

bw1==bw2==bw3==bw4

Linear tuning

l=Monitor[{g=#,Bandwidth[GraphData[#],Method->"Linear"]//Timing,Bandwidth[GraphData[#],Method->"FastLinear"]//Timing}&/@GraphData[;;8],g];

Select[l,#[[2,2]]=!=#[[3,2]]&]

Select[l,#[[2,1]]<#[[3,1]]&]

ratio=#[[3,1]]/#[[2,1]]&/@DeleteCases[l,{{"Empty",_}|"SingletonGraph",__}];

ListPlot[ratio]

Linear vs. Parallel tuning

l=Monitor[{g=#,Bandwidth[GraphData[#],Method->"Parallel"]//Timing,Bandwidth[GraphData[#],Method->"FastLinear"]//Timing}&/@GraphData[8],g];

ratio=#[[2,1]]/#[[3,1]]&/@DeleteCases[l,{{"Empty",_},__}];

Select[l,#[[2,2]]=!=#[[3,2]]&]

ListPlot[ratio]

Parallel tuning

12-node -> 8

Bandwidth[GraphData["DuererGraph"],Method->"Parallel","PermutationOrder"->5]//AbsoluteTiming

Bandwidth[GraphData["DuererGraph"],Method->"Parallel","PermutationOrder"->6]//AbsoluteTiming

Bandwidth[GraphData["DuererGraph"],Method->"Parallel","PermutationOrder"->7]//AbsoluteTiming

Bandwidth[GraphData["DuererGraph"],Method->"Parallel","PermutationOrder"->8]//AbsoluteTiming

Bandwidth[GraphData["DuererGraph"],Method->"Parallel","PermutationOrder"->9]//AbsoluteTiming

Bandwidth[GraphData["DuererGraph"],Method->"Parallel","PermutationOrder"->10]//AbsoluteTiming

timings={{6,29.00364700000000084401108324527740478516`7.4830525240196515},{7,28.94648099999999857345756026916205883026`7.482195687727395},{8,26.0133650000000002933120413217693567276`7.435796447959411},{9,31.89138200000000011868905858136713504791`7.524273252904183},{10,37.60574600000000344834916177205741405487`7.595854121649724}};

fit=Fit[timings,{1,x,x^2},x]

Show[ListPlot[timings],Plot[fit,{x,6,10}]]

13-node -> 10

Bandwidth[GraphData[{"Helm",6}],Method->"Parallel","PermutationOrder"->7]//AbsoluteTiming

Bandwidth[GraphData[{"Helm",6}],Method->"Parallel","PermutationOrder"->8]//AbsoluteTiming

Bandwidth[GraphData[{"Helm",6}],Method->"Parallel","PermutationOrder"->9]//AbsoluteTiming

Bandwidth[GraphData[{"Helm",6}],Method->"Parallel","PermutationOrder"->10]//AbsoluteTiming

Bandwidth[GraphData[{"Helm",6}],Method->"Parallel","PermutationOrder"->11]//AbsoluteTiming

Compute

Finished all up to 600 s on 2023-03-29:

$Version

DateString[]

Length[todo=SortBy[Select[GraphData[All],MissingQ[GraphData[#,"Bandwidth"]]&],GraphData[#,{"V","M"}]&]]

Take[todo,20]

FirstPosition[Sort[GraphData[#,{"V","M","#"}]&/@todo],{121,__}]

p=FirstPosition[todo,{"DifferenceSetIncidence",{73,64,56}},{0}][[1]]

Book + Trapezohedron

Module[{
res={#,Bandwidth[GraphData[#],TimeConstraint->Infinity]//AbsoluteTiming}
},
If[FreeQ[res,$Aborted|$Failed|Failure|GraphData],Print[res]]
]&/@Cases[todo,{"Book"|"Trapezohedron",_}];

Others

Length[todo=SortBy[DeleteCases[Select[GraphData[All],MissingQ[GraphData[#,"Bandwidth"]]&],{"Book"|"Trapezohedron",_}],GraphData[#,{"V","M"}]&]]

p=FirstPosition[todo,"Foster626A",{0}][[1]]

Take[todo,p+{1,20}]

Module[{
res={#,Bandwidth[GraphData[#],TimeConstraint->86400]//AbsoluteTiming}
},
Print[res]
]&/@{{"LindgrenSousselier",64},{"CubicPlanarHypohamiltonian",{70,1}},{"CubicPlanarHypohamiltonian",{70,4}},{"CubicPlanarHypohamiltonian",{70,5}}};

Done