Average Disorder Number

Author

Eric W. Weisstein
August 17, 2022

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

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

©2022 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

Identities

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

GraphDataCountTable

<<MathWorld`Graphs`

GraphDataCountTable["AverageDisorderNumber",{"Goldberg"->130783}]

Parametrized families

Alkane

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

FindSequenceFunction[seq,n]//Factor

AlternatingGroupGraph

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

FindSequenceFunction[seq,n+1]

Andrasfai

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

FindSequenceFunction[seq,n]

Antelope n×n

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

Antiprism

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

((2Entity["Graph",{"Antiprism",n}]["WienerIndex"])/(Entity["Graph",{"Antiprism",n}]["VertexCount"]))

Binomial[n+1,2]

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

Apollonian

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

FindSequenceFunction[seq,n]

Barbell

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

FindSequenceFunction[seq,n]

BlackBishop n×n

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

FindSequenceFunction[Rest@seq,n-1]

Bishop n×n

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

Book

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

FindSequenceFunction[seq,n]//Factor

Bruhat

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

FindSequenceFunction[Rest@seq,n-1]

Camel n×n

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

Centipede

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

FindSequenceFunction[seq,n]//Factor

CocktailParty

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

FindSequenceFunction[Rest@seq,n-1]

Complete

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

((2Entity["Graph",{"Complete",n}]["WienerIndex"])/(Entity["Graph",{"Complete",n}]["VertexCount"]))

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

FindSequenceFunction[seq,n]

CompleteBipartite m×n

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

((2Entity["Graph",{"CompleteBipartite",{m,n}}]["WienerIndex"])/(Entity["Graph",{"CompleteBipartite",{m,n}}]["VertexCount"]))

FullSimplify[%]

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

CompleteBipartite n×n

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

((2Entity["Graph",{"CompleteBipartite",{n,n}}]["WienerIndex"])/(Entity["Graph",{"CompleteBipartite",{n,n}}]["VertexCount"]))

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

FindSequenceFunction[seq,n]//FullSimplify

CompleteTripartite k×m×n

((2Entity["Graph",{"CompleteTripartite",{k,m,n}}]["WienerIndex"])/(Entity["Graph",{"CompleteTripartite",{k,m,n}}]["VertexCount"]))

FullSimplify[%]

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

CompleteTripartite n×n×n

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

((2Entity["Graph",{"CompleteTripartite",{n,n,n}}]["WienerIndex"])/(Entity["Graph",{"CompleteTripartite",{n,n,n}}]["VertexCount"]))

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

FindSequenceFunction[seq,n]//Factor

CrossedPrism

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

FindSequenceFunction[seq,n-1]//Factor

Crown

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

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

CubeConnectedCycle

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

((2Entity["Graph",{"CubeConnectedCycle",n}]["WienerIndex"])/(Entity["Graph",{"CubeConnectedCycle",n}]["VertexCount"]))

Cycle

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

((2Entity["Graph",{"Cycle",n}]["WienerIndex"])/(Entity["Graph",{"Cycle",n}]["VertexCount"]))

seq=Table[GraphData[{"Cycle",n},"AverageDisorderNumber"],{n,3,30}]

FindSequenceFunction[seq,n-2]

Table[Floor[n^2/4],{n,3,30}]

CycleComplement

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

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

DiagonalIntersection

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

FindSequenceFunction[seq,n-2]

Dipyramid

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

FindSequenceFunction[seq,n-2]//FullSimplify

Empty

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

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

FibonacciCube

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

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

Flower

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

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

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

FoldedCube

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

FindSequenceFunction[seq,n]

Gear

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

FindSequenceFunction[seq,n]

Giraffe n×n

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

Goldberg

A130783

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

FindSequenceFunction[seq,n-1]

a(n) = (n+1)*(2^(n-1)-binomial(n-1,n/2)) if n is even else ((n+1)/2)*(2^n-binomial(n,(n+1)/2))

Grid m×n

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

((2Entity["Graph",{"Grid",{m,n}}]["WienerIndex"])/(Entity["Graph",{"Grid",{m,n}}]["VertexCount"]))

Grid n×n

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

((2Entity["Graph",{"Grid",{n,n}}]["WienerIndex"])/(Entity["Graph",{"Grid",{n,n}}]["VertexCount"]))

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

FindSequenceFunction[seq,n]

Grid k×m×n

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

((2Entity["Graph",{"Grid",{k,m,n}}]["WienerIndex"])/(Entity["Graph",{"Grid",{k,m,n}}]["VertexCount"]))

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"AverageDisorderNumber"],
(((k+m+n) (k m n-1))/(3 k m n))
},{n,5},{m,n},{k,m}],2]

Tally[GraphData[{"Grid",{2,3,4}},"DistanceMatrix"]//Normal//Flatten]

Grid n×n×n

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

((2Entity["Graph",{"Grid",{n,n,n}}]["WienerIndex"])/(Entity["Graph",{"Grid",{n,n,n}}]["VertexCount"]))

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

FindSequenceFunction[seq,n]//FullSimplify

HalvedCube

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

FindSequenceFunction[Rest@seq,n]

Hanoi

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

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

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

Helm

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

FindSequenceFunction[seq,n-2]//Factor

Hypercube

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

((2Entity["Graph",{"Hypercube",n}]["WienerIndex"])/(Entity["Graph",{"Hypercube",n}]["VertexCount"]))

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

FindSequenceFunction[seq,n+1]

Keller

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

((2Entity["Graph",{"Keller",n}]["WienerIndex"])/(Entity["Graph",{"Keller",n}]["VertexCount"]))//FullSimplify

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

Table[Piecewise[{{∞,n==1}},(3^n)+(4^n)+n-2],{n,5}]

FindSequenceFunction[Rest@seq,n-1]

King n×n

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

FindSequenceFunction[seq,n]//Factor

Knight m×n

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

((2Entity["Graph",{"Knight",{m,n}}]["WienerIndex"])/(Entity["Graph",{"Knight",{m,n}}]["VertexCount"]))

Knight n×n

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

((2Entity["Graph",{"Knight",{n,n}}]["WienerIndex"])/(Entity["Graph",{"Knight",{n,n}}]["VertexCount"]))

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

Ladder

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

((2Entity["Graph",{"Ladder",n}]["WienerIndex"])/(Entity["Graph",{"Ladder",n}]["VertexCount"]))//FullSimplify

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

FindSequenceFunction[seq,n]//Factor

LadderRung

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

MengerSponge

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

MoebiusLadder

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

((2Entity["Graph",{"MoebiusLadder",n}]["WienerIndex"])/(Entity["Graph",{"MoebiusLadder",n}]["VertexCount"]))//FullSimplify

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

FindSequenceFunction[seq,n-2]//FullSimplify

Mycielski

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

((2Entity["Graph",{"Mycielski",n}]["WienerIndex"])/(Entity["Graph",{"Mycielski",n}]["VertexCount"]))//FullSimplify

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

Table[Piecewise[{{0,n==1}},((216-27 (2^(n+3))-56 (3^n)+81 (4^n))/(18 (3 (2^n)-4)))],{n,11}]

Odd

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

((2Entity["Graph",{"Odd",n}]["WienerIndex"])/(Entity["Graph",{"Odd",n}]["VertexCount"]))//FullSimplify

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

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

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

Pan

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

FindSequenceFunction[seq,n-2]//FullSimplify

Path

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

((2Entity["Graph",{"Path",n}]["WienerIndex"])/(Entity["Graph",{"Path",n}]["VertexCount"]))//FullSimplify

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

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

PathComplement

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

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

Prism

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

((2Entity["Graph",{"Prism",n}]["WienerIndex"])/(Entity["Graph",{"Prism",n}]["VertexCount"]))//FullSimplify

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

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

Queen n×n

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

FindSequenceFunction[seq,n]//Factor

Rook n×n

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

FindSequenceFunction[seq,n]

RookComplement n×n

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

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

SierpinskiCarpet

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

FindSequenceFunction[seq,n]

SierpinskiGasket

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

FindSequenceFunction[seq,n]

SierpinskiTetrahedron

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

FindSequenceFunction[seq,n]

StackedBook

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

FindSequenceFunction[seq,n]//Factor

StackedPrism

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

Star

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

((2Entity["Graph",{"Star",n}]["WienerIndex"])/(Entity["Graph",{"Star",n}]["VertexCount"]))//Factor

FullSimplify[%]

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

FindSequenceFunction[seq,n]//Factor

Sun

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

FindSequenceFunction[seq,n-2]//Factor

Sunlet

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

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

TorusGrid n×n

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

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

Transposition

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

((2Entity["Graph",{"Ladder",n}]["WienerIndex"])/(Entity["Graph",{"Ladder",n}]["VertexCount"]))//FullSimplify

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

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

Triangular

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

FindSequenceFunction[seq,n-1]

TriangularGrid

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

FindSequenceFunction[seq,n+1]//FullSimplify

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombObtuseKnight

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

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

TriangularHoneycombQueen

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

FindSequenceFunction[seq,n]

TriangularHoneycombRook

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

TriangularSnake

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

FindSequenceFunction[seq,n]

Web

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

FindSequenceFunction[seq,n-2]//FullSimplify

Wheel

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

((2Entity["Graph",{"Wheel",n}]["WienerIndex"])/(Entity["Graph",{"Wheel",n}]["VertexCount"]))//Factor

FullSimplify[%]

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

FindSequenceFunction[seq,n-3]//Factor

WheelComplement

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

FindSequenceFunction[seq,n-3]//FullSimplify

WhiteBishop n×n

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

FindSequenceFunction[Rest@seq,n-1]

Factor[%]

Zebra n×n

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

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

Checks

Monitor[DeleteCases[{gn=#,2((GraphData[#,"WienerIndex"])/(GraphData[#,"V"])),AverageDisorderNumber[GraphData[#]]}&/@GraphData["Connected",;;8],{_,x_,x_}],gn]//Timing