Matching Polynomial

Author

Eric W. Weisstein
November 4, 2016

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

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

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

Definition

Sum[(-1)^k a[k]x^(n-2k),{k,Floor[n/2]}]

Special Cases

Andrasfai

(poly=Factor@Table[GraphData[{"Andrasfai",n},"MatchingPolynomial"][x],{n,k0=1,9}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,5]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Antiprism

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Select[GraphData["Antiprism"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="Antiprism"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Apollonian

(poly=Factor@Table[GraphData[{"Apollonian",n},"MatchingPolynomial"][x],{n,k0=1,3}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,2]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["Apollonian"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="Apollonian"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Barbell

(poly=Factor@Table[GraphData[{"Barbell",n},"MatchingPolynomial"][x],{n,k0=3,13}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["Barbell"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="Barbell"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Book

(poly=Factor@Table[GraphData[{"Book",n},"MatchingPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Centipede

(poly=Factor@Table[GraphData[{"Centipede",n},"MatchingPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

..off by factor of z...

Series[z gf,{z,0,4}]

FullSimplify[SeriesCoefficient[z gf,{z,0,n}],n>0]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

CocktailParty

(poly=Factor@Table[GraphData[{"CocktailParty",n},"MatchingPolynomial"][x],{n,k0=1,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,11]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["CocktailParty"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="CocktailParty"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Complete

Entity["Graph",{"Complete",n}]["MatchingPolynomial"][x]

Matching

p=Table[GraphData[{"Complete",n},"MatchingPolynomial"][x],{n,20}]//Factor

FindLinearRecurrence[p]

p=Table[GraphData[{"Complete",n},"MatchingPolynomial"][x],{n,3,20}]//Expand

p-Table[HermiteH[n,x/Sqrt[2]]/2^(n/2),{n,20}]//Expand

Sum[(((-1))^k)((n!)/((2k)!!(n-2k)!))(x^(n-2k)),{k,0,Floor[n/2]}]

Table[Sum[(((-1))^k)((n!)/((2k)!!(n-2k)!))(x^(n-2k)),{k,0,Floor[n/2]}],{n,5}]

Table[HermiteH[n,x/Sqrt[2]]/2^(n/2),{n,5}]//Expand

MatchingGenerating

p=Table[GraphData[{"Complete",n},"MatchingGeneratingPolynomial"][x],{n,20}]//Factor

Table[Sum[((n!)/((2k)!!(n-2k)!))(x^k),{k,0,n}],{n,10}]

FullSimplify[Sum[((n!)/((2k)!!(n-2k)!))(x^k),{k,0,n}],x>0&&n∈Integers&&n>0]

FullSimplify[Sum[((n!)/((2k)!!(n-2k)!))(x^k),{k,0,n}],x>0&&Mod[n,2]==0]

FullSimplify[Sum[((n!)/((2k)!!(n-2k)!))(x^k),{k,0,n}],x>0&&Mod[n,2]==1]

FunctionExpand[%]

Table[(2^(n/2)) (((-(1/x)))^(-n/2)) HypergeometricU[-(n/2),(1/2),-(1/(2 x))],{n,10}]//Expand

ToMatchingGeneratingPolynomial[HermiteH[n,x/Sqrt[2]]/2^(n/2),x]

Table[x^n HermiteH[n,1/(Sqrt[x])],{n,5}]//Expand

Table[n(n-1)/2,{n,30}]

Sum[((n!)/((2k)!!(n-2k)!))(x^k),{k,0,Floor[n/2]}]//FullSimplify

FindLinearRecurrence[p]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["MatchingPolynomial"][x]

(p=Table[GraphData[{"CompleteBipartite",{m,n}},"MatchingPolynomial"][x],{n,5},{m,n}])//Column

l2=Table[LaguerreL[m,x]LaguerreL[n,x],{n,5},{m,n}]//Column

l2=Factor@Table[(((-1))^n)m!n!LaguerreL[m,x]LaguerreL[n,x]/GraphData[{"CompleteBipartite",{m,n}},"MatchingPolynomial"][x],{n,5},{m,n}]//Column

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["MatchingPolynomial"][x]

p=Table[GraphData[{"CompleteBipartite",{n,n}},"MatchingPolynomial"][x],{n,12}]

r=FindLinearRecurrence[p]

l=Expand/@Table[GraphData[{"CompleteBipartite",{n,n}},"MatchingPolynomial"][x],{n,11}]

l2=Table[(-1)^n LaguerreL[n,x^2]n!,{n,11}]

l-l2

FullSimplify[(((-1)^n LaguerreL[n,x^2]n!)/((-1)^n LaguerreL[n,x^2]n!/.n->n-1)),n∈Integers&&n>0]//FunctionExpand

FullSimplify[ToMatchingGeneratingPolynomial[(-1)^n LaguerreL[n,x^2]n!,x]]

l1=Table[GraphData[{"CompleteBipartite",{n,n}},"MatchingGeneratingPolynomial"][x],{n,11}]

l2=Table[n! x^n LaguerreL[n,-(1/x)],{n,11}]//Expand

l1-l2

Select[GraphData["CompleteBipartite"],Equal@@({m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"])&&Expand[GraphData[#,"MatchingPolynomial"][x]-(-1)^n LaguerreL[n,x^2] n!]=!=0&]

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

(poly=Table[GraphData[{"CompleteTripartite",{n,n,n}},"MatchingPolynomial"][x],{n,k0=1,6}])//Column

CoefficientList[#,x]&/@poly

Take[Flatten[%],20]

Reverse[CoefficientList[#,x]]&/@poly

Take[Flatten[%],20]

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,5]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

CrossedPrism

(poly=Factor@Table[GraphData[{"CrossedPrism",n},"MatchingPolynomial"][x],{n,k0=4,20,2}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0/2,Length[coef]-k0/2+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["CrossedPrism"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n=("CrossedPrism"/.GraphData[#,"NotationRules"])/2},LinearRecurrence[{(-1+x) (1+x) (-5+(x^2)),-2 (((-2+(x^2)))^2),4},{5-6 (x^2)+(x^4),(9-8 (x^2)+(x^4)) (1-4 (x^2)+(x^4)),17-186 (x^2)+417 (x^4)-336 (x^6)+117 (x^8)-18 (x^10)+(x^12)},n][[-1]]]]=!=0&]

Crown

(poly=Factor@Table[GraphData[{"Crown",n},"MatchingPolynomial"][x],{n,k0=3,13}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

CubeConnectedCycle

(poly=Factor@Table[GraphData[{"CubeConnectedCycle",n},"MatchingPolynomial"][x],{n,k0=3,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Cycle

Entity["Graph",{"Cycle",n}]["MatchingPolynomial"][x]

MatchingPolynomial

p=Table[GraphData[{"Cycle",n},"MatchingPolynomial"][x],{n,3,20}]//Expand

FindLinearRecurrence[p]

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

p=.

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

Table[(2^(-n)) ((((x-(Sqrt[-4+(x^2)])))^n)+(((x+(Sqrt[-4+(x^2)])))^n)),{n,3,5}]//Expand

Sum[(((-1))^k)(n/(n-k))Binomial[n-k,k](x^(n-2k)),{k,0,Floor[n/2]}]

MatchingGeneratingPolynomial

p=Table[GraphData[{"Cycle",n},"MatchingGeneratingPolynomial"][x],{n,3,20}]//Expand

Table[1+Sum[(n/(n-k))Binomial[n-k,k](x^k),{k,n-1}],{n,10}]

expr=1+Sum[(n/(n-k))Binomial[n-k,k](x^k),{k,n-1}]

FullSimplify[%]

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

Table[(2^n) (((-x))^n) (((1+(Sqrt[1+4 x])))^(-n))+(2^(-n)) (((1+(Sqrt[1+4 x])))^n),{n,6}]//Simplify

FullSimplify[expr,n∈Integers&&n>0]

Empty

Entity["Graph",{"Empty",n}]["MatchingPolynomial"][x]

Table[GraphData[{"Empty",n},"MatchingPolynomial"][x],{n,10}]

FoldedCube

(poly=Factor@Table[GraphData[{"FoldedCube",n},"MatchingPolynomial"][x],{n,k0=2,6}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Gear

(poly=Factor@Table[GraphData[{"Gear",n},"MatchingPolynomial"][x],{n,k0=3,15}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

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

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Grid m×n

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

Grid n×n

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

(poly=Factor@Table[GraphData[{"Grid",{n,n}},"MatchingPolynomial"][x],{n,k0=1,8}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,5]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Grid k×m×n

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

Grid n×n×n

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

(poly=Factor@Table[GraphData[{"Grid",{n,n,n}},"MatchingPolynomial"][x],{n,k0=1,3}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,2]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

HalvedCube

(poly=Factor@Table[GraphData[{"HalvedCube",n},"MatchingPolynomial"][x],{n,k0=1,5}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Hanoi

(poly=Factor@Table[GraphData[{"Hanoi",n},"MatchingPolynomial"][x],{n,k0=1,3}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,2]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Helm

(poly=Factor@Table[GraphData[{"Helm",n},"MatchingPolynomial"][x],{n,k0=3,12}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

%/.{(Sqrt[1-6 (x^2)+(x^4)])->s,1/(Sqrt[1-6 (x^2)+(x^4)])->1/s}//FullSimplify

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n∈Integers&&n>2]

ByteCount/@{(2^(-n)) x ((((-1+(x^2)-(Sqrt[1-6 (x^2)+(x^4)])))^n)+(((-1+(x^2)+(Sqrt[1-6 (x^2)+(x^4)])))^n)+((n ((((-1+(x^2)-(Sqrt[1-6 (x^2)+(x^4)])))^n)-(((-1+(x^2)+(Sqrt[1-6 (x^2)+(x^4)])))^n)))/(Sqrt[1-6 (x^2)+(x^4)]))),-(1/(Sqrt[1-6 (x^2)+(x^4)]))(2^(-1-n)) x ((x^2) ((-5+(x^2)-(Sqrt[1-6 (x^2)+(x^4)])) (((-1+(x^2)-(Sqrt[1-6 (x^2)+(x^4)])))^n)-(-5+(x^2)+(Sqrt[1-6 (x^2)+(x^4)])) (((-1+(x^2)+(Sqrt[1-6 (x^2)+(x^4)])))^n))+(2+n) (-(((-1+(x^2)-(Sqrt[1-6 (x^2)+(x^4)])))^(1+n))+(((-1+(x^2)+(Sqrt[1-6 (x^2)+(x^4)])))^(1+n))))}

Hypercube

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

(poly=Factor@Table[GraphData[{"Hypercube",n},"MatchingPolynomial"][x],{n,k0=1,6}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,4]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Keller

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

(poly=Factor@Table[GraphData[{"Keller",n},"MatchingPolynomial"][x],{n,k0=1,2}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Ladder

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

(poly=Table[GraphData[{"Ladder",n},"MatchingPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

LadderRung

(poly=Factor@Table[GraphData[{"LadderRung",n},"MatchingPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

MoebiusLadder

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>1&&n∈Integers]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Mycielski

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

(poly=Factor@Table[GraphData[{"Mycielski",n},"MatchingPolynomial"][x],{n,k0=1,5}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Odd

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

(poly=Factor@Table[GraphData[{"Odd",n},"MatchingPolynomial"][x],{n,k0=1,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Pan

(poly=Factor@Table[GraphData[{"Pan",n},"MatchingPolynomial"][x],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

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

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>1&&n∈Integers]

Path

Entity["Graph",{"Path",n}]["MatchingPolynomial"][x]

(poly=Factor@Table[GraphData[{"Path",n},"MatchingPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

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

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Sum

Sum[(-1)^k Binomial[n-k,k](x^(n-2k)),{k,0,Floor[n/2]}]//FullSimplify

PermutationStar

(poly=Factor@Table[GraphData[{"PermutationStar",n},"MatchingPolynomial"][x],{n,k0=1,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Prism

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

SierpinskiCarpet

(poly=Factor@Table[GraphData[{"SierpinskiCarpet",n},"MatchingPolynomial"][x],{n,k0=1,2}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

SierpinskiSieve

(poly=Factor@Table[GraphData[{"SierpinskiSieve",n},"MatchingPolynomial"][x],{n,k0=1,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Star

Entity["Graph",{"Star",n}]["MatchingPolynomial"][x]

(poly=Factor@Table[GraphData[{"Star",n},"MatchingPolynomial"][x],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Sun

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

CoefficientList[Take[poly,4],x]//Column

coef=Factor/@FindLinearRecurrence[Drop[poly,2]]

coef=Factor/@FindLinearRecurrence[poly[[1;;;;2]]/(-2+(x^2))]

coef=Factor/@FindLinearRecurrence[poly[[2;;;;2]]]

coef=Factor/@FindPolynomialRecurrence[poly,8]

coef=Factor/@FindPolynomialRecurrence[poly[[1;;;;2]]/(x^2-2),8]

coef=Factor/@FindPolynomialRecurrence[poly[[2;;;;2]],8]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(n0-1))FindGeneratingFunction[poly,z]]

Sunlet

(poly=Factor@Table[GraphData[{"Sunlet",n},"MatchingPolynomial"][x],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>1]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Tetrahedral

(poly=Factor@Table[GraphData[{"Tetrahedral",n},"MatchingPolynomial"][x],{n,k0=6,6}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

TorusGrid n×n

(poly=Factor@Table[GraphData[{"TorusGrid",{n,n}},"MatchingPolynomial"][x],{n,k0=3,7}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Transposition

(poly=Factor@Table[GraphData[{"Transposition",n},"MatchingPolynomial"][x],{n,k0=1,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,2]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Triangular

(poly=Factor@Table[GraphData[{"Triangular",n},"MatchingPolynomial"][x],{n,k0=2,7}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,4]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

TriangularGrid

(poly=Factor@Table[GraphData[{"TriangularGrid",n},"MatchingPolynomial"][x],{n,k0=1,8}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,5]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

Select[GraphData["XXX"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Web

(poly=Factor@Table[GraphData[{"Web",n},"MatchingPolynomial"][x],{n,k0=3,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>2]

Select[GraphData["Web"],Expand[GraphData[#,"MatchingPolynomial"][x]-With[{n="Web"/.GraphData[#,"NotationRules"]},LinearRecurrence[{x (-2+(x^2)),-1+4 (x^2)-2 (x^4),(x^5),-(x^4)},
{x (-2+(x^2)),-2+12 (x^2)-8 (x^4)+(x^6),x (6-35 (x^2)+39 (x^4)-12 (x^6)+(x^8)),2-32 (x^2)+132 (x^4)-172 (x^6)+84 (x^8)-16 (x^10)+(x^12)},n][[-1]]]]=!=0&]

Wheel

Entity["Graph",{"Wheel",n}]["MatchingPolynomial"][x]

(poly=Table[GraphData[{"Wheel",n},"MatchingPolynomial"][x],{n,k0=4,15}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

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

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

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

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>2]

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

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

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

M(G)=I(L(G))

one but not both are defined

GraphData[{"Cage",{4,6}},"MatchingPolynomial"][x]

ToMatchingGeneratingPolynomial[GraphData[{"Cage",{4,6}},"MatchingPolynomial"][x],x]

GraphData[{"Cage",{4,6}},"LineGraphName"]

GraphData[{"Empty",2},"MatchingPolynomial"][x]

Monitor[Select[GraphData["LineGraphName","Defined"],Factor[ToMatchingGeneratingPolynomial[(m=GetGraphData[g=#,"MatchingPolynomial"])[x],x]]=!=GetGraphData[GetGraphData[#,"LineGraphName"],"MatchingPolynomial"][x]&&Head[m]=!=Missing&],g]

Monitor[Select[GraphData["LineGraphName","Defined"],Factor[ToMatchingGeneratingPolynomial[(m=GraphData[g=#,"MatchingPolynomial"])[x],x]]=!=(i=GraphData[GraphData[#,"LineGraphName"],"MatchingPolynomial"])[x]&&Head[m]=!=Missing&&Head[i]=!=GraphData&],g]//Quiet

both are defined

bothdef=Monitor[Select[GraphData[All],Head[GraphData[g=#,"MatchingPolynomial"]]=!=Missing&&Head[l=GraphData[#,"LineGraphName"]]=!=Missing&&UnsameQ[Head[GraphData[l,"MatchingPolynomial"]],Missing,GraphData]&],g];

Length[bothdef]

DeleteCases[{
#,
ToMatchingGeneratingPolynomial[GraphData[#,"MatchingPolynomial"][x],x],
Expand@GraphData[GraphData[#,"LineGraphName"],"MatchingPolynomial"][x]
}&/@bothdef,{_,x_,x_}]

Factor[MatchingPolynomial[Graph[{"CayleyTree",{5,2}}],x]]//Timing

GraphData[{"CayleyTree",{5,2}},"LineGraphName"]

GetGraphData[{"CayleyTree",{5,2}},"File"]

RecognizeGraph[LineGraph[Graph[{"CayleyTree",{5,2}}]]]

Factor[MatchingPolynomial[Graph[{"CayleyTree",{5,2}}],x]]//Timing

Monitor[Select[GraphData["MatchingPolynomial","Defined"],ToMatchingPolynomial[ToMatchingGeneratingPolynomial[m=GraphData[g=#,"MatchingPolynomial"][x],x],x]≠m&],g]

Relation between M(x) and μ(x)

ToMatchingPolynomial[1+6 x+7 (x^2)+(x^3),x]

ToMatchingGeneratingPolynomial[-1+7 (x^2)-6 (x^4)+(x^6),x]

Co-matching graphs

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

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

Length[co]

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

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

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

Examples

http://books.google.com/books?id=2KH25rClXpAC&pg=PA93&lpg=PA93&dq=%22acyclic+polynomial%22&source=web&ots=DZ-OqJ5uO_&sig=eo-3oInGrNNGSDo7LKRtjokAHAw&hl=en&sa=X&oi=book_result&resnum=4&ct=result

46

ShowLabeledGraph[g=AddEdges[AddVertices[Cycle[4],{{2,0},{3,0},{-.2,1.2},{.2,1.2}}],{{1,7},{1,8},{4,5},{5,6}}]]

MatchingPolynomial[g,x]//TraditionalForm

47

ShowLabeledGraph[g=AddEdges[AddVertices[Cycle[3],{{2,0},{2.5,.5},{3,1},{2.5,-.5}}],{{3,4},{4,5},{5,6},{4,7}}]]

MatchingPolynomial[g,x]//TraditionalForm

48

ShowLabeledGraph[g=AddEdges[AddVertices[Cycle[3],{{2,0},{2.5,.5},{3,1},{-.5,-2}}],{{3,4},{4,5},{5,6},{2,7}}]]

MatchingPolynomial[g,x]//TraditionalForm

Tests

Roots are Real

Select[GraphData["MatchingPolynomial","Defined"],Reduce[GraphData[#,"MatchingPolynomial"][x]==0&&Im[x]≠0,x,Complexes]=!=False&]

Coefficient[-8 (x^2)+16 (x^4)-8 (x^6)+(x^8),x,8]

-Coefficient[-8 (x^2)+16 (x^4)-8 (x^6)+(x^8),x,8-2]