Hanoi Graph

Author

Eric W. Weisstein
August 25, 2017

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

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

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

GraphData

GraphData["Hanoi"]

Graphics

GraphicsRow[Table[HanoiGraph[n,PlotLabel->Style[Subscript[H,n],FontFamily->"Times"],VertexSize->{"Scaled",.05},System`VertexStyle->Red,System`EdgeStyle->Black],{n,4}],ImageSize->500]

Table[HanoiGraph[n,VertexLabels->"Name"],{n,3}]

Properties

Acyclic

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

AdjacencyMatrixCount

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

Table[(((3^n)!)/6),{n,5}]

Arboricity

Probably 2

Table[GraphData[{"Hanoi",n},"Arboricity"],{n,5}]

ArcTransitive

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

ArcTransitivity

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

AutomorphismCount

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

BalabanIndex

seq=Table[GraphData[{"Hanoi",n},"BalabanIndex"],{n,3}]//FullSimplify

Bandwidth

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

BridgeCount

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

BurningNumber

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

CharacteristicPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"CharacteristicPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Chordal

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

ChordCount

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

Chordless

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

ChordlessCycleCount

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

FindSequenceFunction[seq,n]

Chords

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

ChromaticallyUnique

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

GraphData[{"ChromaticallyUnique","Hanoi"}]

ChromaticInvariant

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

rows=Import["https://oeis.org/A193233/b193233.txt","Table"][[All,2]];

Take[poly=Factor@Total[Reverse[#]x^Range[0,Length[#]-1]]&/@Split[rows,#1!=0&],All];

seq=Abs[D[poly,x]/.x->1]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

ChromaticNumber

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

ChromaticPolynomial

A288839

A193233 with row ordering reversed

Additional terms from: https://oeis.org/A193233/b193233.txt

(poly=Table[GraphData[{"Hanoi",n},"ChromaticPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x])//Column

CoefficientList[Take[poly,3],x]

Flatten[%]

rows=Import["https://oeis.org/A193233/b193233.txt","Table"][[All,2]]

Take[poly=Factor@Total[Reverse[#]x^Range[0,Length[#]-1]]&/@Split[rows,#1!=0&],4]//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Circumference

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

FindSequenceFunction[seq,n]

Table[(3^n),{n,5}]

Classes

Intersection@@(GraphData[#,"Classes"]&/@GraphData["Hanoi"])

CliqueCount

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

(seq=Table[Length@FindAllCliques[HanoiGraph[n]],{n,7}])//Timing

FindSequenceFunction[seq,n]//FullSimplify

CliqueCoveringNumber

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

FindSequenceFunction[seq,n]

CliqueNumber

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

CliquePolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"CliquePolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

CochromaticGraphNames

Table[GraphData[{"Hanoi",n},"CochromaticGraphNames"],{n,5}]//Column

Select[GraphData["Hanoi"],GraphData[#,"ChromaticallyUnique"]=!=False&]

ComplementOddChordlessCycleCount

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

ConnectedComponentCount

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

ConnectedDominatingSetCount

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

ConnectedDominationNumber

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

ConnectedDominationPolynomial

(poly=Factor@Table[GraphData[{"Hanoi",n},"ConnectedDominationPolynomial"],{n,k0=1,5}]/.f_Function:>f[x])//Column

Take[CoefficientList[DeleteMissing[seq],x],5]

coef=Factor/@FindLinearRecurrence[DeleteMissing[poly]]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

Table[ (2^(-n))((((-(Sqrt[x]) (1+x) (-(Sqrt[x])+(Sqrt[4+x]))))^n)+((((Sqrt[x]) (1+x) ((Sqrt[x])+(Sqrt[4+x]))))^n)),{n,5}]//Factor//Column

Table[(x^(n/2))(((1+x))^n)LucasL[n,(Sqrt[x])],{n,5}]//Factor//Column

gf=Factor[(z^k0)FindGeneratingFunction[DeleteMissing[poly],z]]

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

(poly2=Table[(x^(2 n))+2 n (x^(-2+2 n)) (1+x)+(x^(n/2+1))(((1+x))^n)LucasL[n,(Sqrt[x])],{n,3,11}]//Factor)//Column

FullSimplify[poly2-DeleteMissing[poly]]

FullSimplify[(x^(2 n))+2 n (x^(-2+2 n)) (1+x)+(x^(n/2+1))(((1+x))^n)LucasL[n,(Sqrt[x])]]

ConnectedInducedSubgraphCount

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

FindLinearRecurrence[DeleteCases[seq,_Missing]]

FindSequenceFunction[DeleteCases[seq,_Missing],n]//FullSimplify

gf=x FindGeneratingFunction[DeleteCases[seq,_Missing],x]

ConnectedInducedSubgraphPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"CharacteristicPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,6}]

FullSimplify[poly2-poly]

CrossingNumber

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

CycleCount

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

CyclePolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"CyclePolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Cyclic

Table[GraphData[{"Hanoi",n},"Cyclic"],{n,5}]

CyclomaticNumber

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

FindSequenceFunction[seq,n]

DetourIndex

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

FindSequenceFunction[DeleteMissing@seq,n]

DetourMatrix

MatrixForm/@Table[GraphData[{"Hanoi",n},"DetourMatrix"],{n,5}]

MatrixForm/@Table[SparseArray[{i_,j_}:>Abs[i-j],n],{n,5}]

DetourPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"DetourPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Diameter

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

FindSequenceFunction[seq,n]

DistanceMatrix

MatrixForm/@Table[GraphData[{"Hanoi",n},"DistanceMatrix"],{n,5}]

MatrixForm/@Table[SparseArray[{i_,j_}:>Abs[i-j],n],{n,5}]

DistancePolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"DistancePolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

DistinguishingNumber

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

DominatingSetCount

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

DominationNumber

A122983

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

(seq=Table[DominationNumber[HanoiGraph[n]],{n,6}])//Timing

(seq=Table[DominationNumber[HanoiGraph[n]],{n,7}])//Timing

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//FullSimplify

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

gf=x FindGeneratingFunction[seq,x]

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

DominationPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"DominationPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

EdgeChromaticNumber

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

EdgeConnectivity

Table[GraphData[{"Hanoi",n},"EdgeConnectivity"],{n,5}]

EdgeCount

A029858

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

FindSequenceFunction[seq,n]//FullSimplify

EdgeCoverCount

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

EdgeCoverNumber

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

FindSequenceFunction[seq,n]

EdgeCoverPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"EdgeCoverPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

EulerianCycleCount

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

FaceCount

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

(seq=Table[Length@FindFace[HanoiGraph[n]],{n,6}])//Timing

FindSequenceFunction[Rest@seq,n-1]

Table[Piecewise[{{1,n==1}},(1/2) (1+(3^n))],{n,6}]

FlowPolynomial

Likely pattern by inspection

(poly=Factor[Table[GraphData[{"Hanoi",n},"FlowPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

FractionalChromaticNumber

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

FractionalEdgeChromaticNumber

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

Girth

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

Gonality

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

HamiltonConnected

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

HamiltonDecompositionCount

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

Hamiltonian

Table[GraphData[{"Hanoi",n},"Hamiltonian"],{n,5}]

HamiltonianCycleCount

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

HamiltonianNumber

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

FindSequenceFunction[seq,n]

HamiltonianPathCount

A137889(n)/2

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

2seq

FindSequenceFunction[DeleteMissing@seq,n]

3*a(n-1) + (25*16^n + 64*4^n - 512)/384 for n > 1.

RSolve[{a[1]==6,a[n]==3*a[n-1]+(25*16^n+64*4^n-512)/384},a[n],n]//FullSimplify

RecurrenceTable[{a[1]==6,a[n]==3a[n-1]+(25 16^n+64 4^n-512)/384},a,{n,10}]

Table[(208+16 (3^(n+2))+13 (4^(n+2))+25 (16^n))/312,{n,10}]

HamiltonianWalkCount

Probably 1

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

HararyIndex

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

(seq=Table[HararyIndex[HanoiGraph[n]],{n,7}])//Timing

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

HexagonCount

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

seq=Table[CycleCount[HanoiGraph[n],6],{n,7}]

FindSequenceFunction[Rest@seq,n-1]

IdiosyncraticPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"IdiosyncraticPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x,y]])//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

IndependenceNumber

-------- Original Message --------
Subject: one more...and one by non-ILP
Date: Fri, 18 Nov 2011 08:22:52 -0600
From: Stan Wagon <wagon@macalester.edu>
To: Eric Weisstein <eww@wolfram.com>

Re   {"Hanoi", 5}

Isn't it obvious that ind number is 81. The graph has 81 small triangles, each of which can contain at most one vertex in an ind set. 
The triangles are arranged in the plane so that if, one each triangle, we choose the lowest vertex, that is in ind. set....

So 81?

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

FindSequenceFunction[seq,n]

IndependencePolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"IndependencePolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

CoefficientList[Take[poly,5],x]//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

IndependenceRatio

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

IndependentEdgeSetCount

A286017

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

seq={4,125,4007754,132460031222098852477,4782311037918647241715144272946478084784910628903006412891408,225059171769423175687744072305255139142831483132082163123457465179956142969245590169780815498801423315779792805109943026020568181223921962937686476679317444405928512892552845455329937,};

Rest@NestList[Function[{h,i,j,k},{h^3+3h i^2+3i^2j+j^3,h^2i+2h i j+i^3+2i j^2+i^2k+j^2k,h i^2+2i^2j+h j^2+2i j k+j^3+j k^2,i^3+3i j^2+3j^2k+k^3}]@@#&,{1,1,0,0},5][[All,1]]

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n]

gf=x FindGeneratingFunction[DeleteMissing[seq],x]

IndependentVertexSetCount

A288490

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

{1,3,3,1}.#&/@NestList[Function[{h,i,j,k},{h^3+6h^2i+9h i^2+3h^2j+2i^3+6h i j,h^2i+4h i^2+2h^2j+h^2k+8h i j+3i^3+4i^2j+2h j^2+2h i k,h i^2+4h i j+2i^3+7i^2j+2h i k+3h j^2+4i j^2+2i^2k+2h j k,i^3+6i^2 j+9i j^2+3i^2k+2j^3+6i j k}]@@#&,{1,1,0,0},4]

IntegerLength[{1,3,3,1}.#]&/@NestList[Function[{h,i,j,k},{h^3+6h^2i+9h i^2+3h^2j+2i^3+6h i j,h^2i+4h i^2+2h^2j+h^2k+8h i j+3i^3+4i^2j+2h j^2+2h i k,h i^2+4h i j+2i^3+7i^2j+2h i k+3h j^2+4i j^2+2i^2k+2h j k,i^3+6i^2 j+9i j^2+3i^2k+2j^3+6i j k}]@@#&,{1,1,0,0},7]

IntersectionNumber

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

KirchhoffIndex

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

(seq=Table[KirchhoffIndex[HanoiGraph[n]],{n,5}])//Timing

(seq=Table[KirchhoffIndex[HanoiGraph[n]],{n,6}])//Timing

FindSequenceFunction[seq,n]

KirchhoffSumIndex

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

(seq=Table[KirchhoffSumIndex[HanoiGraph[n]],{n,5}])//Timing

(seq=Table[KirchhoffSumIndex[HanoiGraph[n]],{n,6}])//Timing

FindSequenceFunction[seq,n]

LaplacianMatrix

MatrixForm/@Table[GraphData[{"Hanoi",n},"LaplacianMatrix"],{n,5}]

LaplacianPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"LaplacianPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

LeafCount

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

LongestCycleCount

Same as |HC|

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

LovaszNumber

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

MatchingGeneratingPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"MatchingGeneratingPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

CoefficientList[Take[poly,3],x]

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

MatchingNumber

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

FindSequenceFunction[seq,n]

MatchingPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"MatchingPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

MaximalCliqueCount

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

FindSequenceFunction[seq,n]//FullSimplify

MaximalIndependentEdgeSetCount

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

MaximalIndependentVertexSetCount

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

MaximumCliqueCount

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

FindSequenceFunction[seq,n]

MaximumIndependentEdgeSetCount

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

FindSequenceFunction[DeleteMissing@seq,n]

MaximumIndependentVertexSetCount

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

FindSequenceFunction[DeleteMissing@seq,n]

MaximumLeafNumber

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

MaximumVertexDegree

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

MeanDistance

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

(seq=Table[Mean[Flatten[GraphDistanceMatrix[HanoiGraph[n]]]],{n,7}])//Timing

FindSequenceFunction[seq,n]

MinimumCliqueCoveringCount

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

Table[Length@MinimumCliqueCoverings[HanoiGraph[n]] ,{n,3}]//Timing

Table[Length@MinimumCliqueCoverings[HanoiGraph[n]] ,{n,4}]//Timing

MinimumConnectedDominatingSetCount

Probably 3

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

FindSequenceFunction[seq,n]

MinimumDistinguishingLabelingCount

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

MinimumDominatingSetCount

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

MinimumEdgeCoverCount

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

MinimumVertexDegree

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

MolecularTopologicalIndex

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

(seq=Table[MolecularTopologicalIndex[HanoiGraph[n]],{n,7}])//Timing

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

Nonhamiltonian

Table[GraphData[{"Hanoi",n},"Nonhamiltonian"],{n,5}]

NormalizedLaplacianMatrix

MatrixForm/@Table[GraphData[{"Hanoi",n},"NormalizedLaplacianMatrix"],{n,5}]

OddChordlessCycleCount

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

PathCount

A288796

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

seq={6,279,305868,10210452146391,5764678901089651494212581315486920,7007522073643519244177937570089174585653471798870178330313274704558499562496773948518048745883};

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

PathPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"PathPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

PentagonCount

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

Perfect

Table[GraphData[{"Hanoi",n},"Perfect"],{n,5}]

ProjectivePlaneCrossingNumber

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

Radius

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

(seq=Table[GraphRadius[HanoiGraph[n]],{n,7}])//Timing

FindSequenceFunction[Rest@seq,n-1]

RankPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"RankPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x,y]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

RectilinearCrossingNumber

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

ReliabilityPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"ReliabilityPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

SigmaPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"SigmaPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Skewness

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

SpanningTreeCount

A193136

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

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

SquareCount

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

StabilityIndex

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

(seq=Table[StabilityIndex[HanoiGraph[n]],{n,6}])//Timing

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

TopologicalIndex

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

ToroidalCrossingNumber

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

Traceable

Table[GraphData[{"Hanoi",n},"Traceable"],{n,5}]

TriangleCount

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

FindSequenceFunction[seq,n]

TuttePolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"TuttePolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x,y]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Untraceable

Table[GraphData[{"Hanoi",n},"Untraceable"],{n,5}]

VertexConnectivity

Table[GraphData[{"Hanoi",n},"VertexConnectivity"],{n,5}]

VertexCount

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

FindSequenceFunction[seq,n]

VertexCoverNumber

vertex cover number == vertex count - independence number

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

FindSequenceFunction[seq,n]

VertexCoverPolynomial

(poly=Factor[Table[GraphData[{"Hanoi",n},"VertexCoverPolynomial"],{n,k0=1,kmax=5}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

VertexDegrees

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

VertexTransitive

Table[GraphData[{"Hanoi",n},"VertexTransitive"],{n,5}]

WienerIndex

A290004

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

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

Table[GraphData[{"Hanoi",n},"V"],{n,5}]

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

gf=((3 x (1-11 x+28 (x^2)+24 (x^3)))/((1-3 x) (1-9 x) (1-18 x) (1-5 x+2 (x^2))));

Series[((3 x (1-11 x+28 (x^2)+24 (x^3)))/((1-3 x) (1-9 x) (1-18 x) (1-5 x+2 (x^2)))),{x,0,20}]

seq=CoefficientList[Series[((3(1-11 x+28 (x^2)+24 (x^3)))/((1-3 x) (1-9 x) (1-18 x) (1-5 x+2 (x^2)))),{x,0,20}],x]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{35,-395,1761,-2916,972},{3,72,1419,26580,487839},20]

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

Table[ (3/1003) (2^(-n))( (34-3 (Sqrt[17])) (((5-(Sqrt[17])))^n)+ (((5+(Sqrt[17])))^n) (34+3 (Sqrt[17])))-((3^(n+1))/10)+ (9^n)((233/885) (2^n)-(1/6)),{n,10}]//Expand

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

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

Table[GraphData[{"Hanoi",n},"V"],{n,5}]

Table[(3^n),{n,5}]

2Limit[(((3/1003) (2^(-n))( (34-3 (Sqrt[17])) (((5-(Sqrt[17])))^n)+ (((5+(Sqrt[17])))^n) (34+3 (Sqrt[17])))-((3^(n+1))/10)+ (9^n)((233/885) (2^n)-(1/6)))/(((((3^n)))^2)((2^n)-1))),n->∞]

WienerSumIndex

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

FindSequenceFunction[DeleteMissing@seq,n]

GraphData

GraphClassString

GraphClassString[GraphData["Hanoi"]]

GraphDataString

Do[Print[GraphDataString[HanoiGraph[n],
"Name"->ToString[n]<>"-Hanoi graph",
"StandardName"->{"Hanoi",n},
"Classes"->{"Hanoi"},
"NotationRules"->{"Hanoi"->n},
TimeConstraint->60,
Debug->True
]],{n,5}]