Flow Polynomial

Author

Eric W. Weisstein
July 11, 2008

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

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

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

Examples

(Subscript[K, 3,3])

Factor[FlowPolynomial[Graph["K3,3"],u]]//TraditionalForm

(Subscript[O, 3])

Factor[FlowPolynomial[Graph[{"Odd",3}],u]]//TraditionalForm

Classes

?FindPolynomialRecurrence

XXXTemplate

poly=DeleteCases[Table[GraphData[{"Crown",n},"FlowPolynomial"][u],{n,n0=4,20}],_Missing[_]]

r=Factor/@FindPolynomialRecurrence[poly]

(Subscript[p, n])[u]==r.Table[(Subscript[p, n-k])[u],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Andásfai

Antiprism

poly=DeleteCases[Table[GraphData[{"Antiprism",n},"FlowPolynomial"][u],{n,n0=3,20}],_Missing[_]]

r=Factor/@FindPolynomialRecurrence[poly,4]

LinearRecurrence[{11-8 u+2 (u^2),-(5-4 u+(u^2)) (7-4 u+(u^2)),29-44 u+27 (u^2)-8 (u^3)+(u^4),-(((-2+u))^2)}

(Subscript[p, n])[u]==r.Table[(Subscript[p, n-k])[u],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Table[(2^(-n)) ((2^n)+(2^n) ((((((-2+u))^2)))^n)-3 (2^n) u+(2^n) (u^2)-(((6-4 u+(u^2)-(-2+u) (Sqrt[8+(-4+u) u])))^n)+u (((6-4 u+(u^2)-(-2+u) (Sqrt[8+(-4+u) u])))^n)+(-1+u) (((6-4 u+(u^2)+(-2+u) (Sqrt[8+(-4+u) u])))^n)),{n,3,10}]//Expand//Factor

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Apollonian

Barbell

Bridged -> 0

Book

poly=Table[GraphData[{"Book",n},"FlowPolynomial"][u],{n,n0=4,20}]

r=Factor/@FindLinearRecurrence[poly]

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Centipede

Tree -> 0

CocktailParty

poly=DeleteCases[Table[GraphData[{"CocktailParty",n},"FlowPolynomial"][u],{n,n0=3,20}],_Missing[_]]//Quiet

Length[poly]

r=Factor/@FindPolynomialRecurrence[poly,4]

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Complete

poly=DeleteCases[Table[GraphData[{"Complete",n},"FlowPolynomial"][u],{n,n0=3,20}],_Missing[_]]

Length[poly]

r=Factor/@FindPolynomialRecurrence[poly,4]

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

CompleteBipartite

CompleteTripartite

CrossedPrism

poly=DeleteCases[Table[GraphData[{"Crown",n},"FlowPolynomial"][u],{n,n0=3,20}],_Missing[_]]

r=Factor/@FindPolynomialRecurrence[poly,4]

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Crown

poly=DeleteCases[Table[GraphData[{"Crown",n},"FlowPolynomial"][u],{n,n0=3,20}],_Missing[_]]

r=Factor/@FindPolynomialRecurrence[poly,2]

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

CubeConnectedCycle

Cycle

p=Table[GraphData[{"Cycle",n},"FlowPolynomial"][u],{n,3,20}]

FoldedCube

Gear

nxn Grid

nxnxn Grid

HalvedCube

Hanoi

Helm

Bridged -> 0

poly=DeleteCases[Table[GraphData[{"Helm",n},"FlowPolynomial"][u],{n,n0=4,20}],_Missing[_]]

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Hypercube

poly=DeleteCases[Table[GraphData[{"Hypercube",n},"FlowPolynomial"][u],{n,n0=1,20}],(_Missing|_GraphData)[_]]//Quiet

r=Factor/@FindPolynomialRecurrence[poly,2]

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

King

poly=DeleteCases[Table[GraphData[{"King",{n,n}},"FlowPolynomial"][u],{n,n0=2,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindPolynomialRecurrence[poly,3]

(Subscript[p, n])[u]==r.Table[(Subscript[p, n-k])[u],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Knight

Ladder

poly=DeleteCases[Table[GraphData[{"Ladder",n},"FlowPolynomial"][u],{n,n0=1,20}],_Missing[_]]

r=Factor/@FindPolynomialRecurrence[poly,2]

(u-1)(((u-2))^(n-1))

LadderRung

Bridged -> 0

poly=DeleteCases[Table[GraphData[{"LadderRung",n},"FlowPolynomial"][u],{n,n0=1,20}],_Missing[_]]

Lattice

MoebiusLadder

poly=DeleteCases[Table[GraphData[{"MoebiusLadder",n},"FlowPolynomial"][u],{n,n0=3,20}],_Missing[_]]

r=Factor/@FindPolynomialRecurrence[poly,3]

(Subscript[p, n])[u]==r.Table[(Subscript[p, n-k])[u],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Mycielski

Odd

poly=DeleteCases[Table[GraphData[{"Odd",n},"FlowPolynomial"][u],{n,n0=1,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindPolynomialRecurrence[poly]

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Pan

Bridged -> 0

Path

Bridged -> 0

PermutationStar

Prism

poly=DeleteCases[Table[GraphData[{"Prism",n},"FlowPolynomial"][u],{n,n0=3,20}],_Missing[_]]

r=Factor/@FindPolynomialRecurrence[poly,3]

(Subscript[p, n])[u]==r.Table[(Subscript[p, n-k])[u],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Queen

Sierpinski

Star

Bridged -> True

Sun

poly=DeleteCases[Table[GraphData[{"Sun",n},"FlowPolynomial"][u],{n,n0=3,20}],_Missing[_]]

r=Factor/@FindPolynomialRecurrence[poly,4]

(Subscript[p, n])[u]==r.Table[(Subscript[p, n-k])[u],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Sunlet

Bridged -> 0

Tetrahedral

TorusGrid

Triangular

Web

Bridged -> 0

Wheel

poly=Table[GraphData[{"Wheel",n},"FlowPolynomial"][u],{n,n0=4,20}]

r=Factor/@FindLinearRecurrence[poly]

RSolve[Prepend[Table[p[n+n0-1,u]==poly[[n]],{n,Length[r]}],p[n,u]==r.Table[p[n-k,u],{k,Length[r]}]],p[n,u],n]//FullSimplify

Expand[Subtract@@@Table[{(((-1))^(1+n)) (-2+u)+(((-2+u))^(-1+n)),poly[[n-n0+1]]},{n,n0+1,10}]]