Reliability Polynomial

Author

Eric W. Weisstein
June 20, 2023

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

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

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

Code

Godsil and Royle pp. 355-358

ReliabilityPolynomial[g_Graph,p_]:=Module[{n=V[g],m=M[g],c=ConnectedComponentCount[g],x,y},
(1-p)^(n-c)p^(m-n+c)Cancel[TuttePolynomial[g,{x,y}]/.{x->1,y->1/p}]
]

Expression on p. 358 is wrong

ReliabilityPolynomial2[g_Graph,p_]:=Module[{n=V[g],m=M[g],c=ConnectedComponentCount[g],x,y},
(1-p)^(n-c)p^(m-n+c)Cancel[(x-1)^(n-1) RankPolynomial[g,{1/(x-1),y-1}]]/.{x->1,y->1/p}
]

ReliabilityPolynomialPage[g_,p_]:=Module[{e=Edges[g],m=M[g]},
Factor[Total[p^M[#](1-p)^(m-M[#])&/@Select[FromUnorderedPairs/@Subsets[e],ConnectedQ[#]&&V[#]==V[g]&]]]
]

Examples

Petersen

Factor[ReliabilityPolynomial[Graph["PetersenGraph"],p]]

Factor[ReliabilityPolynomial2[Graph["PetersenGraph"],p]]

-(((-1+p))^9) (1+9 p+45 (p^2)+155 (p^3)+390 (p^4)+696 (p^5)+704 (p^6))//TraditionalForm

ReliabilityPolynomial[Graph["PetersenGraph"],p,Method->"Page"]//Timing

ReliabilityPolynomial[Graph["PetersenGraph"],p,Method->"RankPolynomial"]//Timing

Diamond

ReliabilityPolynomial[Graph["DiamondGraph"],p]

Factor[ReliabilityPolynomial[Graph["DiamondGraph"],p]/.p->1-p]

Co-Reliability Graphs

l=Monitor[Sort[{GetGraphData[#,"ReliabilityPolynomial"][x],g=#}&/@GetGraphData[All]],g];//Timing

Length[co=Select[Split[l,First[#1]==First[#2]&],Length[#]>1&]]

ll=Sort[{GetGraphData[#[[1,2]],"V"],#[[1,1]],#[[All,2]]}&/@co];

TableForm[Take[Most[ll],-5],TableDepth->2]

TableForm[Take[ll,30],TableDepth->2]

Special Cases

Andasfai

p=Table[GraphData[{"Andrasfai",n},"ReliabilityPolynomial"][x],{n,4}]

FindLinearRecurrence[p]

Antiprism

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

(poly=Table[GraphData[{"Antiprism",n},"ReliabilityPolynomial"],{n,3,25}]/.f_Function:>f[x])//Column

coef=FindLinearRecurrence[DeleteMissing@poly]

Length[coef]

Take[poly,6]

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

Apollonian

p=Table[GraphData[{"Apollonian",n},"ReliabilityPolynomial"][x],{n,3}]

r=FindLinearRecurrence[p]

Barbell

p=Table[GraphData[{"Barbell",n},"ReliabilityPolynomial"][x],{n,3,5}]

r=Factor/@FindLinearRecurrence[p]

p=Refine[Table[(Sqrt[GraphData[{"Barbell",n},"ReliabilityPolynomial"][x]/-(((x-1))^(2n-1))]),{n,3,5}],x>0]//Factor

r=Factor/@FindLinearRecurrence[p]

Book

l=Table[GraphData[{"Book",n},"ReliabilityPolynomial"][x],{n,3,8}]

r=Factor/@FindLinearRecurrence[l]

p=.

FullSimplify[RSolve[{p[n]==(((-1+x))^2) (1+5 x)p[n-1]-3 (((-1+x))^4) x (1+2 x)p[n-2],p[3]==l[[1]],p[4]==l[[2]]},p[n],n],n∈Integers&&n>0]

CocktailParty

p=Table[GraphData[{"CocktailParty",n},"ReliabilityPolynomial"][x],{n,4}]

r=FindLinearRecurrence[p]

Complete

p=Table[GraphData[{"Complete",n},"ReliabilityPolynomial"][x],{n,8}]//Simplify

FindLinearRecurrence[p]

p=Table[GraphData[{"Complete",n},"ReliabilityPolynomial"][x]/(((-1+x))^(n-1))(((-1))^(n+1)),{n,8}]//Simplify

FindLinearRecurrence[p]

CompleteBipartite

p=Table[GraphData[{"CompleteBipartite",{n,n}},"ReliabilityPolynomial"][x],{n,5}]

r=FindLinearRecurrence[p]

CrossedPrism

p=Table[GraphData[{"CrossedPrism",n},"ReliabilityPolynomial"][x],{n,4,8,2}]

r=Factor/@FindLinearRecurrence[p]

Crown

p=Table[GraphData[{"Crown",n},"ReliabilityPolynomial"][x],{n,3,5}]

r=Factor/@FindLinearRecurrence[p]

CubeConnectedCycle

p=Table[GraphData[{"CubeConnectedCycle",n},"ReliabilityPolynomial"][x],{n,3,4}]

Cycle

p=Table[GraphData[{"Cycle",n},"ReliabilityPolynomial"][x],{n,3,20}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

p[1,x]=.

RSolve[{p[n,x]==(-1+2 x-(x^2)) p[-2+n,x]+(2-2 x) p[-1+n,x],p[3,x]==1-3 (x^2)+2 (x^3),p[4,x]==1-6 (x^2)+8 (x^3)-3 (x^4)
},p[n,x],n]//FullSimplify

p-Table[(((1-x))^(-1+n)) (1+(-1+n) x),{n,3,20}]//Expand

FoldedCube

p=Table[GraphData[{"FoldedCube",n},"ReliabilityPolynomial"][x],{n,2,4}]

r=Factor/@FindLinearRecurrence[p]

Gear

p=Table[GraphData[{"Gear",n},"ReliabilityPolynomial"][x],{n,3,8}]

r=Factor/@FindLinearRecurrence[p]

p=Table[GraphData[{"Gear",n},"ReliabilityPolynomial"][x]/(((x-1))^(2n)),{n,3,8}]

r=FindLinearRecurrence[p]

r=FindPolynomialRecurrence[p,3]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==p[n,x]==(x^2) p[-3+n,x]+(-2 x-3 (x^2)) p[-2+n,x]+(1+4 x) p[-1+n,x],
p[3,x]==1+6 x+18 (x^2)+25 (x^3),
p[4,x]==1+8 x+32 (x^2)+72 (x^3)+79 (x^4),
p[5,x]==1+10 x+50 (x^2)+150 (x^3)+270 (x^4)+241 (x^5)},p[n,x],n]//FullSimplify

FullSimplify[(2^(-n)) (-(2^(1+n)) (x^n)+(((1+3 x-(Sqrt[1+x (2+9 x)])))^n)+(((1+3 x+(Sqrt[1+x (2+9 x)])))^n))(((x-1))^(2n))]

Table[(2^(-n)) (((-1+x))^(2 n)) (-(2^(1+n)) (x^n)+(((1+3 x-(Sqrt[1+x (2+9 x)])))^n)+(((1+3 x+(Sqrt[1+x (2+9 x)])))^n)),{n,3,8}]//Expand//Factor

(2^(-n)) (((-1+x))^(2 n)) (-(2^(1+n)) (x^n)+(((1+3 x-(Sqrt[1+x (2+9 x)])))^n)+(((1+3 x+(Sqrt[1+x (2+9 x)])))^n))/.(Sqrt[1+x (2+9 x)])->t//FullSimplify

(2^(-n)) (((x-1))^(2 n)) ((((-t+3 x+1))^n)+(((t+3 x+1))^n)-(2^(n+1)) (x^n))

p=Table[(2^(-n)) (((-1+x))^(2 n)) (-(2^(1+n)) (x^n)+(((1+3 x-(Sqrt[1+x (2+9 x)])))^n)+(((1+3 x+(Sqrt[1+x (2+9 x)])))^n)),{n,3,20}]//Expand//Factor

r=FindLinearRecurrence[p,x,a,"RecurrenceOrder"->3,"CoefficientOrder"->8]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

2-Grid

p=Table[GraphData[{"Grid",{n,n}},"ReliabilityPolynomial"][x],{n,4}]

FindLinearRecurrence[p]

3-Grid

p=Table[GraphData[{"Grid",{n,n,n}},"ReliabilityPolynomial"][x],{n,2}]

FindLinearRecurrence[p]

HalvedCube

p=Table[GraphData[{"HalvedCube",n},"ReliabilityPolynomial"][x],{n,4}]

r=FindLinearRecurrence[p]

Hanoi

p=Table[GraphData[{"Hanoi",n},"ReliabilityPolynomial"][x],{n,2}]

Helm

l=Table[GraphData[{"Helm",n},"ReliabilityPolynomial"][x],{n,3,8}]

FindLinearRecurrence[p]

FindPolynomialRecurrence[p,3]

p=.

FullSimplify[RSolve[{p[n]==(((-1+x))^2) (1+3 x)p[n-1]-2 (((-1+x))^4) x (1+x)p[n-2]+(((-1+x))^6) (x^2)p[n-3],p[3]==l[[1]],p[4]==l[[2]],p[5]==l[3[]]},p[n],n],n∈Integers&&n>2&&x∈Reals]

Hypercube

p=Table[GraphData[{"Hypercube",n},"ReliabilityPolynomial"][x],{n,3}]//Factor

Factor/@FindLinearRecurrence[p]

Ladder

p=Table[GraphData[{"Ladder",n},"ReliabilityPolynomial"][x],{n,15}]

Factor/@FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==-x p[-2+n,x]+(1+3 x) p[-1+n,x],p[1,x]==-1,p[2,x]==-1-3x},p[n,x],n]//FullSimplify

p-Table[(((2^(-n)) ((((1+3 x-(Sqrt[1+x (2+9 x)])))^n)-(((1+3 x+(Sqrt[1+x (2+9 x)])))^n)))/(Sqrt[1+x (2+9 x)]))(((x-1))^(2n-1)),{n,8}]//Expand

(((2^(-n)) ((((1+3 x-(Sqrt[1+x (2+9 x)])))^n)-(((1+3 x+(Sqrt[1+x (2+9 x)])))^n)))/(Sqrt[1+x (2+9 x)]))(((x-1))^(2n-1))//TraditionalForm

LadderRung

p=Table[GraphData[{"LadderRung",n},"ReliabilityPolynomial"][x],{n,20}]

MoebiusLadder

p=Table[GraphData[{"MoebiusLadder",n},"ReliabilityPolynomial"][x],{n,3,8}]

r=FindLinearRecurrence[p]

r=FindPolynomialRecurrence[p,2]

p=Table[-GraphData[{"MoebiusLadder",n},"ReliabilityPolynomial"][x]/(((x-1))^(2n-1)),{n,3,8}]

r=FindLinearRecurrence[p]

r=Factor/@FindPolynomialRecurrence[p,3]

Mycielski

p=Table[GraphData[{"Mycielski",n},"ReliabilityPolynomial"][x],{n,4}]

r=FindLinearRecurrence[p]

Odd

p=Table[GraphData[{"Odd",n},"ReliabilityPolynomial"][x],{n,2,3}]

r=Factor/@FindLinearRecurrence[p]

Pan

p=Table[GraphData[{"Pan",n},"ReliabilityPolynomial"][x],{n,3,7}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(-1+2 x-(x^2)) p[-2+n,x]+(2-2 x) p[-1+n,x],
p[3,x]==-(((-1+x))^3) (1+2 x),
p[4,x]==(((-1+x))^4) (1+3 x)},p[n,x],n]//FullSimplify

Path

p=Table[GraphData[{"Path",n},"ReliabilityPolynomial"][x],{n,20}]

r=Factor/@FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

PermutationStar

p=Table[GraphData[{"PermutationStar",n},"ReliabilityPolynomial"][x],{n,3}]

r=Factor/@FindLinearRecurrence[p]

Prism

p=Table[GraphData[{"Prism",n},"ReliabilityPolynomial"][x],{n,3,8}]

r=FindLinearRecurrence[p]

r=Factor/@FindPolynomialRecurrence[p,3]

p=Table[-GraphData[{"Prism",n},"ReliabilityPolynomial"][x]/(((x-1))^(2n-1)),{n,3,8}]

r=Factor/@FindLinearRecurrence[p]

r=Factor/@FindPolynomialRecurrence[p,2]

Sierpinski

p=Table[GraphData[{"Sierpinski",n},"ReliabilityPolynomial"][x],{n,2}]

Square

p=Table[GraphData[{"Square",n},"ReliabilityPolynomial"][x],{n,3}]

r=Factor/@FindLinearRecurrence[p]

Star

p=Table[GraphData[{"Star",n},"ReliabilityPolynomial"][x],{n,3,20}]

r=FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

Sun

(poly=Table[GraphData[{"Sun",n},"ReliabilityPolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Sunlet

p=Table[GraphData[{"Sunlet",n},"ReliabilityPolynomial"][x],{n,3,13}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p-Table[(((1-x))^(2n-1))(1+(n-1)x),{n,3,13}]//Expand

Tetrahedral

p=Table[GraphData[{"Tetrahedral",n},"ReliabilityPolynomial"][x],{n,6,10}]

TorusGrid

p=Table[GraphData[{"TorusGrid",{n,n}},"ReliabilityPolynomial"][x],{n,3,4}]

r=FindLinearRecurrence[p]

Triangular

p=Table[GraphData[{"Triangular",n},"ReliabilityPolynomial"][x],{n,2,4}]

r=FindLinearRecurrence[p]

Web

p=Table[GraphData[{"Web",n},"ReliabilityPolynomial"][x],{n,3,6}]

FindLinearRecurrence[p]

Factor/@FindPolynomialRecurrence[p,2]

Wheel

p=Table[GraphData[{"Wheel",n},"ReliabilityPolynomial"][x],{n,4,14}]

r=Factor/@FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(x^2) p[-3+n,x]+(-2 x-2 (x^2)) p[-2+n,x]+(1+3 x) p[-1+n,x],
p[4,x]==1+3 x+6 (x^2)+6 (x^3),p[5,x]==1+4 x+10 (x^2)+16 (x^3)+14 (x^4),p[6,x]==1+5 x+15 (x^2)+30 (x^3)+40 (x^4)+30 (x^5)},p[n,x],n]//FullSimplify

p-Table[(((1-x))^(n-1))(1/x)(2^(-1-n)) (-(2^(2+n)) (x^n)+(((1+2 x-(Sqrt[1+4 (x^2)])))^n)+2 x (((1+2 x-(Sqrt[1+4 (x^2)])))^n)+(Sqrt[1+4 (x^2)]) (((1+2 x-(Sqrt[1+4 (x^2)])))^n)+(1+2 x) (((1+2 x+(Sqrt[1+4 (x^2)])))^n)-(Sqrt[1+4 (x^2)]) (((1+2 x+(Sqrt[1+4 (x^2)])))^n)),{n,4,14}]//Expand

(((1-x))^(n-1))(1/x)(2^(-1-n)) (-(2^(2+n)) (x^n)+(((1+2 x-(Sqrt[1+4 (x^2)])))^n)+2 x (((1+2 x-(Sqrt[1+4 (x^2)])))^n)+(Sqrt[1+4 (x^2)]) (((1+2 x-(Sqrt[1+4 (x^2)])))^n)+(1+2 x) (((1+2 x+(Sqrt[1+4 (x^2)])))^n)-(Sqrt[1+4 (x^2)]) (((1+2 x+(Sqrt[1+4 (x^2)])))^n))/.{(Sqrt[1+4 (x^2)])->t,1/(Sqrt[1+4 (x^2)])->1/t}//FullSimplify