Disorder Number

Author

Eric W. Weisstein
October 8, 2024

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

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

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

Source

Sela Fried.  The disorder number of a graph. 7 Aug 2022.  https://arxiv.org/abs/2208.03788

GraphDataCountTable

<<MathWorld`Graphs`

GraphDataCountTable["DisorderNumber",{"Antiprism"->014848,"Barbell"->016921,"Centipede"->227786,"CocktailParty"->016789,"Complete"->001477,"CompleteBipartite"->016813,"CompleteTripartite"->016933,"Crown"->016885,"Cycle"->000982,"CycleComplement"->005843,"Dipyramid"->005408,{"Grid",2}->179094,"Hypercube"->271771,"Ladder"->028347,"LucasCube"->166956,"MoebiusLadder"->245524,"Pan"->376901,"Path"->047838,"PathComplement"->005843,"PlummerToft"->005843,"Prism"->035608,"Star"->004273,"Wheel"->005408}]

Parametrized families

Alkane

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

FindSequenceFunction[seq,n]

AlternatingGroupGraph

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

Andrasfai

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]//FullSimplify

Antelope n×n

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

Antiprism

Probably A014848

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

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

Table[n^2-Floor[n/2],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"DisorderNumber"],{n,5}]

FindSequenceFunction[seq,n]

Barbell

A016921

Inferred for n > 6:

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Factor

Table[6n-5,{n,3,20}]

BlackBishop n×n

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

(seq=Table[MinorCount[BlackBishopGraph[n,n]],{n,50}])//Timing

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

Bishop n×n

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

Book

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

FindSequenceFunction[seq,n]

Bruhat

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

FindSequenceFunction[seq,n]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"DisorderNumber"],{n,10}]

Centipede

Possibly A227786

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

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

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

FindGeneratingFunction[DeleteMissing@seq,x]//Head

CocktailParty

A016789

Inferred for n > 5:

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

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

Complete

A001477

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

Inferred for n > 9:

seq=Table[GraphData[{"Complete",n},"DisorderNumber"],{n,30}]

FindSequenceFunction[DeleteMissing@seq,n]

CompleteBipartite m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"DisorderNumber"],
2(m+n)-3
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

A016813

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

Inferred for n > 4:

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

Table[4n-3,{n,20}]

CompleteTripartite k×m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"DisorderNumber"],
2(m+n+k-2)
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

Inferred for these:

CompleteTripartite n×n×n

A016933

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

Inferred for n > 3:

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

Table[6n-4,{n,10}]

CrossedPrism

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

FindSequenceFunction[seq,n-1]//Factor

Crown

Possibly A016885

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

Table[5n+3,{n,20}]

CubeConnectedCycle

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

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

Cycle

A000982

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

seq=Table[GraphData[{"Cycle",n},"DisorderNumber"],{n,3,25}]

https://arxiv.org/abs/2208.03788v3

Table[DisorderNumber[CycleGraph[n]],{n,3,9}]//Timing

Table[Ceiling[((((n-1))^2)/2)],{n,3,9}]

CycleComplement

A005843

Inferred for n > 10:

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

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

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

DiagonalIntersection

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

Dipyramid

A005408

Inferred for n > 8:

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

FindSequenceFunction[Drop[DeleteMissing@seq,2],n-4]//Factor

Table[2n+1,{n,3,20}]

Empty

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

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

FibonacciCube

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

FindSequenceFunction[DeleteMissing@seq,n]//Factor

Table[3-4 n+2 (n^2),{n,15}]

Flower

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

FoldedCube

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

FindSequenceFunction[seq,n]

Gear

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

FindSequenceFunction[seq,n]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"DisorderNumber"],{n,10}]

Goldberg

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

Grid m×n

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

https://arxiv.org/abs/2208.03788v3

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"DisorderNumber"],
Piecewise[{
{0,m==n==1},
{12,Min[m,n]==2&&Max[m,n]==3},
{32,Min[m,n]==2&&Max[m,n]==5},
{((m n(m+n))/2)-3,Mod[m,2]==0&&Mod[n,2]==0},{((m n(m+n))/2)-((m+n)/2)-1,Mod[m,2]==1&&Mod[n,2]==1},{((m n(m+n))/2)-(m/2)-1,Mod[m,2]==0&&Mod[n,2]==1},
{((m n(m+n))/2)-(n/2)-1,Mod[m,2]==1&&Mod[n,2]==0}}]
},{n,5},{m,n}],1],{_,x_,x_}]

Grid n×n

A179094

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

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

FindSequenceFunction[seq,n]

FindSequenceFunction[seq,n]

https://arxiv.org/abs/2208.03788v3

Table[DisorderNumber[GridGraph[{n,n}]],{n,3}]//Timing

Table[Piecewise[{{0,n==1},{(n^3)-3,Mod[n,2]==0},{(n^3)-n-1,Mod[n,2]==1}}],{n,4}]

Grid k×m×n

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

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"DisorderNumber"],
XXX
},{n,5},{m,n},{k,m}],2]

Grid n×n×n

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

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

FindSequenceFunction[seq,n]//FullSimplify

HalvedCube

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

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]

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

Hanoi

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

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

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

Helm

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

FindSequenceFunction[seq,n]

Hypercube

A271771

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

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

FindSequenceFunction[seq,n+1]

https://arxiv.org/pdf/2208.03788

Table[DisorderNumber[HypercubeGraph[n]],{n,0,3}]//Timing

seq=Table[Piecewise[{{0,n==0}},((2^(n-1))-1)(2n-1)+n],{n,0,10}]

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

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

gf=FindGeneratingFunction[seq,x]

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

Keller

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

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

FindSequenceFunction[seq,n]

King n×n

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

FindSequenceFunction[seq,n]//Factor

Knight m×n

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

Knight n×n

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

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

Ladder

A028347

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

Inferred for n > 6:

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

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

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

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

From Grid m×n (that result is stated only for m,n>=3)

Subtract@@{(n+3)(n-1),(n+2)n-2}//Expand

DeleteCases[Table[{n,GraphData[{"Ladder",n},"DisorderNumber"],Piecewise[{
{12,n==3},
{32,n==5},
{(n+3)(n-1),Mod[n,2]==0},
{(n+2)n-2,Mod[n,2]==1}}]},{n,20}],{_,x_,x_}]

LadderRung

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

LucasCube

Possibly A166956

seq=Table[GraphData[{"LucasCube",n},"DisorderNumber"],{n,15}]

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

MengerSponge

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

MoebiusLadder

Possibly A245524 for n > 3

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

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

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

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

Mycielski

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

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

Odd

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

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

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

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

Pan

A376901

Inferred for n > 10:

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

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

seq=Table[(n(n-1)+5+(-1)^n)/2,{n,54}]

ToString[%]//StringLength

coef=FindLinearRecurrence[seq]

OEISRecurrenceIndexString[coef]

OEISRecurrenceString[coef]

gf=x FindGeneratingFunction[seq,x]

StringReplace[ToString[gf,InputForm]," "->""]

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

Path

A047838

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

https://arxiv.org/abs/2208.03788v3

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

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

Table[DisorderNumber[PathGraph[Range@n]],{n,3,9}]//Timing

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

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

PathComplement

A005843

Inferred for n > 10:

seq=Table[GraphData[{"PathComplement",n},"DisorderNumber"],{n,3,20}]

FindSequenceFunction[DeleteMissing@Drop[seq,3],n-5]

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

PlummerToft

Possibly A005843 for n > 3:

seq=Table[GraphData[{"PlummerToft",n},"DisorderNumber"],{n,20}]

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

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

Prism

Likely A035608

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

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

Table[n^2+n-1-Floor[(n-1)/2],{n,3,25}]

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

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

Queen n×n

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

FindSequenceFunction[seq,n]

Rook n×n

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

FindSequenceFunction[seq,n]

RookComplement n×n

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

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

SierpinskiCarpet

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

FindSequenceFunction[seq,n]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"DisorderNumber"],{n,5}]

FindSequenceFunction[seq,n]

SierpinskiTetrahedron

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

FindSequenceFunction[seq,n]

StackedBook

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

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"DisorderNumber"],{n,3,5}]

Star

A004273

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

Inferred for n > 8:

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

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

Table[Piecewise[{{0,n==1}},2n-3],{n,25}]

Sun

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

Length@DeleteMissing@seq+2

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

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

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

Sunlet

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

Length@DeleteMissing@seq+2

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

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

TorusGrid n×n

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

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

Transposition

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

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

FindSequenceFunction[Rest@seq,n-1]//FullSimplify

Trapezohedron

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

Length@DeleteMissing@seq+2

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

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

Triangular

seq=Table[GraphData[{"Triangular",n},"DisorderNumber"],{n,2,10}]

FindSequenceFunction[seq,n-1]

TriangularGrid

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

FindSequenceFunction[seq,n+1]//FullSimplify

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

FindSequenceFunction[seq,n]

TriangularHoneycombRook

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

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"DisorderNumber"],{n,1,20,2}]

FindSequenceFunction[seq,n]

Web

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

Wheel

A005408

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

Inferred for n > 9:

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

Factor[2(n-2)+1]

Table[Piecewise[{{3,n==4},{6,n==5}},2n-3],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"DisorderNumber"],{n,4,20}]

WhiteBishop n×n

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

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

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"DisorderNumber"],{n,10}]

Example

{"Path", 5}

g=PathGraph[Range[5],VertexLabels->Automatic]

d=GraphDistanceMatrix[g]

d[[Sequence@@#]]&/@Partition[{3,1,5,2,4},2,1]

Total[%]

d[[Sequence@@#]]&/@Partition[Reverse@{3,1,5,2,4},2,1]

Total[%]

SymmetricallyDistinctVertices[PathGraph[Range[5]],4]

SymmetricallyDistinctLabelings[PathGraph[Range[5]],Range]

Disorders[g_Graph]:=Module[{walks=Permutations[VertexList[g]],d=GraphDistanceMatrix[g]},
Function[walk,Total[d[[Sequence@@#]]&/@Partition[walk,2,1]]]/@walks
]

DisorderNumber[g_Graph]:=Max[Disorders[g]]

AverageDisorderNumber[g_Graph]:=Mean[Disorders[g]]

dis=Disorders[PathGraph[Range[5]]]

Max[dis]

Mean[dis]

DisorderNumber[PathGraph[Range[5]]]

AverageDisorder[PathGraph[Range[5]]]