Kirchhoff Index

Author

Eric W. Weisstein
April 19, 2020

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

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

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

Missing

DateString[]

GraphData["KirchhoffIndex","Missing"]

Table

GraphDataCountTable["KirchhoffIndex"]

Parametrized families

Andrasfai

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

(seq=Table[KirchhoffIndex[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}},"KirchhoffIndex"],{n,10}]

Antiprism

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

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

(seq=Table[KirchhoffIndex[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},"KirchhoffIndex"],{n,6}]

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

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

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

Bishop n×n

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

BlackBishop n×n

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

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

(seq=Table[KirchhoffIndex[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},"KirchhoffIndex"],{n,6}]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

Centipede

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

FindSequenceFunction[seq,n]//Factor

CocktailParty

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

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

Complete

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

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

CompleteBipartite k×n

Entity["Graph",{"CompleteBipartite",{k,n}}]["KirchhoffIndex"]

CompleteBipartite n×n

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

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

FindSequenceFunction[seq,n]

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

FindSequenceFunction[seq,n]

CrossedPrism

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

FindSequenceFunction[seq,n-1]//Factor

Crown

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

FindSequenceFunction[seq,n-2]//Factor

CubeConnectedCycle

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

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

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

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

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

Cycle

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

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

FindSequenceFunction[seq,n-2]//Factor

DiagonalIntersection

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

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

Dipyramid

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

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

Empty

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

seq=Table[GraphData[{"Empty",n},"KirchhoffIndex"],{n,20}]

FibonacciCube

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

(seq=Table[KirchhoffIndex[FibonacciCubeGraph[n]],{n,10}])//Timing

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

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

Fiveleaper n×n

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

FoldedCube

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

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

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

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

Gear

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

(seq=Table[KirchhoffIndex[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}}]["KirchhoffIndex"]

Grid n×n

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

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

(seq=Table[KirchhoffIndex[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}}]["KirchhoffIndex"]

Grid n×n×n

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

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

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

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

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

HalvedCube

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

(seq=Table[KirchhoffIndex[HalvedCubeGraph[n]],{n,8}])//Timing

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

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

Hanoi

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

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

Hypercube

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

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

Keller

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

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

King m×n

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

King n×n

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

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

(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}}]["KirchhoffIndex"]

Knight n×n

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

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

(seq=Table[KirchhoffIndex[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}]["KirchhoffIndex"]

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

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

(seq=Table[KirchhoffIndex[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},"KirchhoffIndex"],{n,20}]

MengerSponge

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

MoebiusLadder

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

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

(seq=Table[KirchhoffIndex[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}]["KirchhoffIndex"]

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

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

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

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

Odd

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

seq=Table[GraphData[{"Odd",n},"KirchhoffIndex"],{n,6}]

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

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

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

Pan

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

Table[KirchhoffIndex[PanGraph[n]],{n,2,20}]

FindSequenceFunction[seq,n-2]//Factor

Path

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

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

FindSequenceFunction[seq,n]//Factor

PathComplement

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

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

PermutationStar

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

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

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

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

Prism

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

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

(seq=Table[KirchhoffIndex[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}},"KirchhoffIndex"],{n,10}]

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

Rook n×n

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

FindSequenceFunction[seq,n]//Factor

RookComplement n×n

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

Through[{Numerator,Denominator}[Drop[seq,2]]]

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

SierpinskiCarpet

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

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

SierpinskiSieve

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

FindSequenceFunction[seq,n]//Head

SierpinskiTetrahedron

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

FindSequenceFunction[seq,n]//Head

StackedBook m×n

StackedBook n×n

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

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

Star

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

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

Sun

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

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

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

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

Sunlet

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

FindSequenceFunction[seq,n-2]//Factor

Tetrahedral

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

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

FindSequenceFunction[seq,n-5]//Factor

TorusGrid n×n

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

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

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

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

Transposition

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

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

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

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

Triangular

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

FindSequenceFunction[seq,n-1]//Factor

TriangularGrid

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

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

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

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

TriangularHoneycombAcuteKnight

TriangularHoneycombBishop

TriangularHoneycombObtuseKnight

TriangularHoneycombQueen

TriangularHoneycombRook

TriangularSnake

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

FindSequenceFunction[seq,n]//Factor

Web

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

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

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

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

Wheel

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

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

(seq=Table[KirchhoffIndex[WheelGraph[n]],{n,4,40}])//Timing

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

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

WhiteBishop n×n

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

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

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

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

Numeric computation for large graphs

{"SierpinskiCarpet", 2}

KirchhoffIndex[GraphData[{"SierpinskiCarpet",2}]]

GraphData[{"SierpinskiCarpet",2},"KirchhoffIndex"]

KirchhoffIndex[GraphData[{"SierpinskiCarpet",2}],WorkingPrecision->100]

Rationalize[%]

{"SierpinskiCarpet", 3}

KirchhoffIndex[GraphData[{"SierpinskiCarpet",3}]]//Timing

GraphData[{"SierpinskiCarpet",3},"KirchhoffIndex"]

Rationalize[KirchhoffIndex[GraphData[{"SierpinskiCarpet",3}],WorkingPrecision->1000]]//Timing

Checks

<<MathWorld`Graphs`

GraphData["KirchhoffIndex","Missing"]

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

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

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

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

Numerical

DeleteCases[Monitor[
{#,Chop[#2-#3]}&@@@({
gn=#,
GraphData[#,"KirchhoffIndex"],
KirchhoffIndex[GraphData[#],WorkingPrecision->20]
}&/@GraphData["Connected",;;100]),gn
],
{_,0}]//Timing

DeleteCases[Monitor[
{#,Chop[#2-#3]}&@@@({
gn=#,
GraphData[#,"KirchhoffIndex"],
KirchhoffIndex[GraphData[#],WorkingPrecision->20]
}&/@GraphData["Connected",101;;200]),gn
],
{_,0}]//Timing

DeleteCases[Monitor[
{#,Chop[#2-#3]}&@@@({
gn=#,
GraphData[#,"KirchhoffIndex"],
KirchhoffIndex[GraphData[#],WorkingPrecision->20]
}&/@GraphData["Connected",201;;500]),
gn
],
{_,0}]//Timing

DeleteCases[Monitor[
{#,Chop[#2-#3]}&@@@({
gn=#,
GraphData[#,"KirchhoffIndex"],
KirchhoffIndex[GraphData[#],WorkingPrecision->20]
}&/@GraphData["Connected",501;;1000]),
gn
],
{_,0}]//Timing

DeleteCases[Monitor[
{#,Chop[#2-#3]}&@@@({
gn=#,
GraphData[#,"KirchhoffIndex"],
KirchhoffIndex[GraphData[#],WorkingPrecision->20]
}&/@GraphData["Connected",1001;;2000]),
gn
],
{_,0}]//Timing

SortBy[GraphData[2001;;],GraphData[#,"V"]&]

DeleteCases[Monitor[
{#,Chop[#2-#3]}&@@@({
gn=#,
GraphData[#,"KirchhoffIndex"],
KirchhoffIndex[GraphData[#],WorkingPrecision->20]
}&/@{{"Kneser",{14,5}},{"CubeConnectedCycle",8},{"SierpinskiTetrahedron",6},{"Cage",{5,12}},{"Cage",{12,8}},{"Kneser",{14,6}}}),
gn
],
{_,0}]//Timing