Kirchhoff Sum Index

Author

Eric W. Weisstein
April 19, 2020

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

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

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

Missing

DateString[]

GraphData["KirchhoffSumIndex","Missing"]

Parametrized families

GraphDataCountTable["KirchhoffSumIndex"]

Andrasfai

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

(seq=Table[KirchhoffSumIndex[AndrasfaiGraph[n]],{n,20}])//Timing

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

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

Antelope n×n

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

Antiprism

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

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

(seq=Table[KirchhoffSumIndex[AntiprismGraph[n]],{n,3,50}])//Timing

FindSequenceFunction[Drop[seq,2],n-4]//Head//Timing

FindLinearRecurrence[Drop[seq,2]]//Head//Timing

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

Apollonian

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

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

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

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

Bishop n×n

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

BlackBishop n×n

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

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

(seq=Table[KirchhoffSumIndex[BlackBishopGraph[n,n]],{n,20}])//Timing

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,5}]

Bruhat

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

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

Centipede

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

FindSequenceFunction[seq,n]//Factor

CocktailParty

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

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

Complete

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

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

FindSequenceFunction[seq,n]

CompleteBipartite m×n

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

CompleteBipartite n×n

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

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"KirchhoffSumIndex"],{n,10}]

FindSequenceFunction[l,n]

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

FindSequenceFunction[seq,n]

CrossedPrism

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

(seq=Table[KirchhoffSumIndex[CrossedPrismGraph[2n]],{n,2,20}])//Timing

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

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

Crown

seq=Table[GraphData[{"Crown",n},"KirchhoffSumIndex"],{n,3,10}]

FindSequenceFunction[seq,n-2]//Factor

CubeConnectedCycle

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

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

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

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

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

Cycle

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

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

FindSequenceFunction[seq,n-2]//FullSimplify

DiagonalIntersection

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

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

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"KirchhoffSumIndex"],{n,3,14}]

FindSequenceFunction[seq,n-2]

FindSequenceFunction[Drop[seq,1],n-3]//Factor

Empty

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

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

FibonacciCube

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

(seq=Table[KirchhoffSumIndex[FibonacciCubeGraph[n]],{n,12}])//Timing

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

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

Fiveleaper n×n

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

FoldedCube

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

(seq=Table[KirchhoffSumIndex[FoldedCubeGraph[n]],{n,2,9}])//Timing

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

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

Gear

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

(seq=Table[KirchhoffSumIndex[GearGraph[n]],{n,3,30}])//Timing

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

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

Grid m×n

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

Grid n×n

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

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

(seq=Table[KirchhoffSumIndex[System`GridGraph[{n,n}]],{n,15}])//Timing

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

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

Grid k×m×n

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

Grid n×n×n

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

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

(seq=Table[KirchhoffSumIndex[System`GridGraph[{n,n,n}]],{n,8}])//Timing

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

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

HalvedCube

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

(seq=Table[KirchhoffSumIndex[HalvedCubeGraph[n]],{n,9}])//Timing

seq={0,1,3,(23/3),(115/6),(13123/270),(5698/45),(21445/63),(1190507/1260),(85183627/31500),(25079197/3150),(3749088082/155925),(7720370957/103950)};

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

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

Hanoi

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

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,3}]

Hypercube

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

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

(seq=Table[KirchhoffSumIndex[HypercubeGraph[n]],{n,9}])//Timing

seq={1,4,(227/18),(334/9),(96661/900),(140663/450),(10194871/11025),(30803116/11025),(6854577137/793800),(10830776629/396900),(4228148644729/48024900),(3474650044156/12006225),(7849737483616471/8116208100)};

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

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

Keller

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

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

King m×n

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

King n×n

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

FindSequenceFunction[Drop[seq,1],n-1]//Head//Timing

(seq=Table[KirchhoffIndex[KingGraph[n,n]],{n,12}])//Timing

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,5}]

Knight m×n

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

Knight n×n

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

seq=Table[GraphData[{"Knight",{n,n}},"KirchhoffSumIndex"],{n,10}]

(seq=Table[KirchhoffSumIndex[KnightGraph[n,n]],{n,13}])//Timing

FindSequenceFunction[Drop[seq,3],n-3]//Head//Timing

FindSequenceFunction[Drop[seq,4],n-4]//Head//Timing

Ladder

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

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

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,5}]

(seq=Table[KirchhoffSumIndex[LadderGraph[n]],{n,50}])//Timing

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,5}]

LadderRung

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

MengerSponge

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

MoebiusLadder

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

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

(seq=Table[KirchhoffSumIndex[MoebiusLadder[n]],{n,3,50}])//Timing

FindSequenceFunction[Drop[seq,2],n-4]//Head//Timing

FindLinearRecurrence[Drop[seq,2]]//Head//Timing

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

Mycielski

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

seq=Table[GraphData[{"Mycielski",n},"KirchhoffSumIndex"],{n,10}]

(seq=Table[KirchhoffSumIndex[MycielskiGraph1[n]],{n,8}])//Timing

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

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

Odd

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

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

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

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

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

Pan

Find closed form for nonlinear recurrence

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

(seq=Table[KirchhoffSumIndex[PanGraph[n]],{n,3,50}])//Timing

FindSequenceFunction[seq,n-2]

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

Path

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

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

f=FindSequenceFunction[l,n]//Factor

PathComplement

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

FindSequenceFunction[Drop[seq,3],n-3]//Head//Timing

PermutationStar

seq=Table[GraphData[{"PermutationStar",n},"KirchhoffSumIndex"],{n,6}]

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

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

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

Prism

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

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

(seq=Table[KirchhoffSumIndex[PrismGraph[n]],{n,3,50}])//Timing

FindSequenceFunction[Drop[seq,2],n-4]//Head//Timing

FindLinearRecurrence[Drop[seq,2]]//Head//Timing

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

Queen n×n

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

FindSequenceFunction[Drop[seq,1],n-1]//Head//Timing

Rook n×n

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

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

RookComplement n×n

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

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

SierpinskiCarpet

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

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

SierpinskiSieve

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

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

SierpinskiTetrahedron

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

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

StackedBook m×n

StackedBook n×n

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

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

Star

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

seq=Table[GraphData[{"Star",n},"KirchhoffSumIndex"],{n,20}]

FindSequenceFunction[seq,n]

Sun

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

(seq=Table[KirchhoffSumIndex[SunGraph[n]],{n,3,40}])//Timing

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

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

Sunlet

Convert DifferenceRoot to closed form

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

(seq=Table[KirchhoffSumIndex[SunletGraph[n]],{n,3,50}])//Timing

FindSequenceFunction[seq,n-2]

Tetrahedral

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

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

FindSequenceFunction[seq,n-5]//Factor

TorusGrid n×n

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

(seq=Table[KirchhoffSumIndex[TorusGridGraph[n,n]],{n,3,15}])//Timing

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

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

Triangular

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

(seq=Table[KirchhoffSumIndex[TriangularGraph[n]],{n,2,15}])//Timing

FindSequenceFunction[seq,n-1]//Factor

TriangularGrid

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

(seq=Table[KirchhoffSumIndex[TriangularGridGraph[n]],{n,15}])//Timing

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

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

TriangularSnake

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

FindSequenceFunction[seq,n]//Factor

Web

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

(seq=Table[KirchhoffSumIndex[WebGraph[n]],{n,3,30}])//Timing

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

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

Wheel

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

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

(seq=Table[KirchhoffSumIndex[WheelGraph[n]],{n,4,50}])//Timing

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

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

WhiteBishop n×n

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

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

(seq=Table[KirchhoffSumIndex[WhiteBishopGraph[n,n]],{n,2,20}])//Timing

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,5}]

Checks

GraphData["KirchhoffSumIndex","Missing"]

DeleteCases[{#,GraphData[#,"KirchhoffSumIndex"],KirchhoffSumIndex[GraphData[#]]}&/@GraphData[;;20],{_,x_,x_}]//Timing

DeleteCases[{#,GraphData[#,"KirchhoffSumIndex"],KirchhoffSumIndex[GraphData[#]]}&/@GraphData[;;50],{_,x_,x_}]//Timing

DeleteCases[{#,GraphData[#,"KirchhoffSumIndex"],KirchhoffSumIndex[GraphData[#]]}&/@GraphData[;;100],{_,x_,x_}]//Timing