Stability Index

Author

Eric W. Weisstein
May 3, 2009

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

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

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

Special Classes

Andrasfai

l=Table[GraphData[{"Andrasfai",n},"StabilityIndex"],{n,10}]

FindSequenceFunction[l]

FindSequenceFunction[Drop[l,1],n-1]

Antiprism

l=Table[GraphData[{"Antiprism",n},"StabilityIndex"],{n,20}]//Quiet

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

Apollonian

l=Table[GraphData[{"Apollonian",n},"StabilityIndex"],{n,6}]

FindSequenceFunction[l]

CocktailParty

l=Table[GraphData[{"CocktailParty",n},"StabilityIndex"],{n,20}]//Quiet

FullSimplify[FindSequenceFunction[Drop[l,1],n-1],n∈Integers]

CompleteBipartite

l=Table[GraphData[{"CompleteBipartite",{n,n}},"StabilityIndex"],{n,10}]

FindSequenceFunction[l,n]

Complete

l=Table[GraphData[{"Complete",n},"StabilityIndex"],{n,20}]

FindSequenceFunction[l,n]

FullSimplify[FindSequenceFunction[Drop[l,2],n-2],n ∈Integers]

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

CompleteTriipartite

l=Table[GraphData[{"CompleteTripartite",{n,n,n}},"StabilityIndex"],{n,10}]//Quiet

FindSequenceFunction[Take[l,6],n]

CrossedPrism

l=Table[GraphData[{"CrossedPrism",2n},"StabilityIndex"],{n,10}]//Quiet

FullSimplify[FindSequenceFunction[Drop[l,1]][n-1],n∈Integers&&n>1]

Crown

l=Table[GraphData[{"Crown",n},"StabilityIndex"],{n,10}]//Quiet

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

CubeConnectedCycle

l=Table[GraphData[{"CubeConnectedCycle",n},"StabilityIndex"],{n,10}]//Quiet

FindSequenceFunction[Take[l,{3,7}]][n-2]

Cycle

l=Table[GraphData[{"Cycle",n},"StabilityIndex"],{n,20}]//Quiet

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

Drop[l,2][[2;;-1;;2]]

FullSimplify[FindSequenceFunction[Drop[l,2][[2;;-1;;2]]][n-2],n∈Integers&&n>2]

Table[Piecewise[{{2,Mod[n,2]==1},{5((Fibonacci[n/2])^2),Mod[n,2]==0}}],{n,20}]

FindSequenceFunction[%,n]

Empty

l=Table[GraphData[{"Empty",n},"StabilityIndex"],{n,20}]

FindSequenceFunction[l][n]

FoldedCube

l=Table[GraphData[{"FoldedCube",n},"StabilityIndex"],{n,10}]//Quiet

FindSequenceFunction[Drop[l,1]][n-1]

Gear

l=Table[GraphData[{"Gear",n},"StabilityIndex"],{n,20}]//Quiet

Grid n×n

l=Table[GraphData[{"Grid",{n,n}},"StabilityIndex"],{n,10}]

FindSequenceFunction[l]

FindSequenceFunction[l[[2;;-1;;2]]]

Grid n×n×n

l=Table[GraphData[{"Grid",{n,n,n}},"StabilityIndex"],{n,10}]

FindSequenceFunction[l]

HalvedCube

l=Table[GraphData[{"HalvedCube",n},"StabilityIndex"],{n,10}]

FindSequenceFunction[l]

Hypercube

l=Table[GraphData[{"Hypercube",n},"StabilityIndex"],{n,10}]

FindSequenceFunction[l]

Lattice

l=Table[GraphData[{"Lattice",{n,n}},"StabilityIndex"],{n,10}]//Quiet

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

MöbiusLadder

l=Table[GraphData[{"MoebiusLadder",n},"StabilityIndex"],{n,20}]//Quiet

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

Mycielski

l=Table[GraphData[{"Mycielski",n},"StabilityIndex"],{n,10}]

FindSequenceFunction[l,n]

Odd

l=Table[GraphData[{"Odd",n},"StabilityIndex"],{n,6}]

FindSequenceFunction[l,n]

Pan

l=Table[GraphData[{"Pan",n},"StabilityIndex"],{n,20}]//Quiet

FullSimplify[FindSequenceFunction[Drop[l,2],n-2],n∈Integers&&n>2]

Drop[l,2][[1;;-1;;2]]

FullSimplify[FindSequenceFunction[Drop[l,2][[1;;-1;;2]],n-1],n∈Integers]

Table[Piecewise[{{0,Mod[n,2]==0},{2Fibonacci[n+1],Mod[n,2]==1}}],{n,20}]

FullSimplify[FindSequenceFunction[%,n],n∈Integers&&n>0]

Path

l=Table[GraphData[{"Path",n},"StabilityIndex"],{n,20}]

Drop[l,2][[2;;-1;;2]]

FindSequenceFunction[%]

Table[Piecewise[{{0,Mod[n,2]==1},{Fibonacci[n+1],Mod[n,2]==0}}],{n,20}]

PermutationStar

l=Table[GraphData[{"PermutationStar",n},"StabilityIndex"],{n,10}]//Quiet

FindSequenceFunction[Take[l,6],n]

Prism

l=Table[GraphData[{"Prism",n},"StabilityIndex"],{n,20}]//Quiet

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

Square

l=Table[GraphData[{"Square",n},"StabilityIndex"],{n,10}]

FindSequenceFunction[l,n]//Factor

Star

l=Table[GraphData[{"Star",n},"StabilityIndex"],{n,20}]

FindSequenceFunction[l,n]

Sun

l=Table[GraphData[{"Sun",n},"StabilityIndex"],{n,20}]//Quiet

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

Sunlet

l=Table[GraphData[{"Sunlet",n},"StabilityIndex"],{n,20}]//Quiet

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

Refine[FullSimplify[%,n∈Integers],n∈Integers]

Tetrahedral

l=Table[GraphData[{"Tetrahedral",n},"StabilityIndex"],{n,10}]//Quiet

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

TorusGrid

l=Table[GraphData[{"TorusGrid",{n,n}},"StabilityIndex"],{n,10}]//Quiet

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

Triangular

l=Table[GraphData[{"Triangular",n},"StabilityIndex"],{n,10}]//Quiet

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

Web

l=Table[GraphData[{"Web",n},"StabilityIndex"],{n,20}]//Quiet

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

Wheel

l=Table[GraphData[{"Wheel",n},"StabilityIndex"],{n,20}]//Quiet

FindSequenceFunction[Drop[l,3]][n-3]

FindSequenceFunction[Drop[l,4]][n-4]

Examples

32

34

44

ShowLabeledGraph[g=AddEdges[AddVertices[Cycle[6],{{-2,0},{2,0},{3,0}}],{{3,7},{6,8},{8,9}}]]

StabilityIndex[g]

45

Petersen

StabilityIndex[Graph["PetersenGraph"]]

V[Graph["PetersenGraph"]]

I^-10 CharacteristicPolynomial[ToAdjacencyMatrix[Graph["PetersenGraph"]],x]/.x->I

Hard

GraphData["HundredTwentyCellGraph","CharacteristicPolynomial"][x]

poly=-(((-3+(Sqrt[5])-2 x))^30) (((1+(Sqrt[5])-2 x))^24) (((5+(Sqrt[5])-2 x))^9) (((1+3 (Sqrt[5])-2 x))^4) (((3+(Sqrt[13])-2 x))^16) (((-1+(Sqrt[21])-2 x))^16) (((-1+(Sqrt[2])-x))^48) ((((Sqrt[5])-x))^24) (-4+x) (((-1+x))^40) (x^18) (((1+x))^8) (((2+x))^8) (((1+(Sqrt[2])+x))^48) ((((Sqrt[5])+x))^24) (((-5+(Sqrt[5])+2 x))^9) (((-1+(Sqrt[5])+2 x))^24) (((3+(Sqrt[5])+2 x))^30) (((-1+3 (Sqrt[5])+2 x))^4) (((-3+(Sqrt[13])+2 x))^16) (((1+(Sqrt[21])+2 x))^16) ((Simplify[Expand[(x-Root[4-7 #1-((#1)^2)+((#1)^3)&,1]) (x-Root[4-7 #1-((#1)^2)+((#1)^3)&,2]) (x-Root[4-7 #1-((#1)^2)+((#1)^3)&,3])]])^25)((Simplify[Expand[(x-Root[8-7 #1-((#1)^2)+((#1)^3)&,1]) (x-Root[8-7 #1-((#1)^2)+((#1)^3)&,2]) (x-Root[8-7 #1-((#1)^2)+((#1)^3)&,3])]])^36);

poly

Total[Abs[CoefficientList[poly,x][[1;;-1;;2]]]]

Checks

GraphData["StabilityIndex","Missing"]

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

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