Hosoya Index

Author

Eric W. Weisstein
March 9, 2016

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

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

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

Code

HosoyaIndex[g_Graph]:=Module[{x},
Total[Abs[First/@Partition[CoefficientList[MatchingPolynomial[g,x],x],2,2,{1,1},{}]]]
]

HosoyaIndex0[g_Graph]:=ToMatchingGeneratingPolynomial[MatchingPolynomial[g,x],x]/.x->1

HosoyaIndex1[g_Graph]:=Total[Abs[CoefficientList[MatchingPolynomial[g,x],x]]]

Special Classes

Andrasfai

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

FindSequenceFunction[Most@l,n]

Antiprism

l=Table[GraphData[{"Antiprism",n},"HosoyaIndex"],{n,3,25}]//Quiet

FindSequenceFunction[l][n-2]

FindLinearRecurrence[l]

FindGeneratingFunction[{4,3,15,51,191,708,2631,9775,36319,134943,501380,1862875,6921503,25716811,95550687,355018116,1319068095,4900991135,18209608887,67657713855,251381908996},x]//Factor

Factor[((4-9 x-6 (x^2)+(x^3))/(1-3 x-3 (x^2)+(x^3)+(x^4)))-4]

Series[-((x (-3-6 x+3 (x^2)+4 (x^3)))/(1-3 x-3 (x^2)+(x^3)+(x^4))),{x,0,10}]

RSolve[a[n]==3a[n-1]+3a[n-2]-a[n-3]-a[n-4]&&a[3]==51&&a[4]==191&&a[5]==708&&a[6]==2631,a[n],n]//FullSimplify

Roots[1+x-3 (x^2)-3 (x^3)+(x^4)==0,x,Quartics->False]

Table[((Root[1+#1-3 ((#1)^2)-3 ((#1)^3)+((#1)^4)&,1])^n)+((Root[1+#1-3 ((#1)^2)-3 ((#1)^3)+((#1)^4)&,2])^n)+((Root[1+#1-3 ((#1)^2)-3 ((#1)^3)+((#1)^4)&,3])^n)+((Root[1+#1-3 ((#1)^2)-3 ((#1)^3)+((#1)^4)&,4])^n),{n,10}]//RootReduce

Table[RootSum[1+#1-3 ((#1)^2)-3 ((#1)^3)+((#1)^4)&,#^n&],{n,20}]

LinearRecurrence[{3,3,-1,-1},{3,15,51,191},{1,30}]

Apollonian

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

CocktailParty

l=DeleteCases[Table[GraphData[{"CocktailParty",n},"HosoyaIndex"],{n,20}],_Missing]//Quiet

FindSequenceFunction[l,n]

FindGeneratingFunction[l,x]

FindLinearRecurrence[l]

CompleteBipartite

l=DeleteCases[Table[GraphData[{"CompleteBipartite",{n,n}},"HosoyaIndex"],{n,10}],_Missing]

Table[n! LaguerreL[n,-1],{n,10}]

FindSequenceFunction[l,n]

FindGeneratingFunction[l,x]

FindLinearRecurrence[l]

Table[n! LaguerreL[n,-1],{n,10}]

Complete

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

FindSequenceFunction[l,n]//FunctionExpand

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

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

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

Table[(n/2)!2^(n/2) LaguerreL[n/2,-1/2,-1/2],{n,2,20,2}]

N[%]

l[[2;;All;;2]]

FindSequenceFunction[l[[2;;All;;2]],n]

FindSequenceFunction[l[[1;;All;;2]],n]

Table[Piecewise[{{0,Mod[n,2]==1},{(n/2)!*2^(n/2)*LaguerreL[n/2,-1/2,-1/2],Mod[n,1]==0}}],{n,30}]

CompleteTriipartite

l=DeleteCases[Table[GraphData[{"CompleteTripartite",{n,n,n}},"HosoyaIndex"],{n,10}],_Missing|_GraphData]//Quiet

CrossedPrism

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

l/12

FindSequenceFunction[l,n-1]

FindLinearRecurrence[l]

FindGeneratingFunction[l,x]

Crown

l=DeleteCases[Table[GraphData[{"Crown",n},"HosoyaIndex"],{n,3,10}],_Missing]//Quiet

FindSequenceFunction[l,n-2]

FindGeneratingFunction[l,x]

FindLinearRecurrence[l]

Table[n!*Sum[((-1)^m/m!)Binomial[n-m,j]/j!,{m,0,n},{j,0,n-m}],{n,30}]

Sum[Binomial[n-m,j]/j!,{j,0,n-m}]

Table[n!Sum[((((-1))^m)/(m!))Hypergeometric1F1[m-n,1,-1],{m,0,n}],{n,30}]

FunctionExpand[Hypergeometric1F1[m-n,1,-1]]

Table[n!Sum[((((-1))^m)/(m!))LaguerreL[-m+n,-1],{m,0,n}],{n,30}]

Sum[((-1)^m/m!)LaguerreL[-m+n,-1],{m,0,n}]

Sum[((-1)^m/m!)Hypergeometric1F1[m-n,1,-1],{m,0,n}]

CubeConnectedCycle

l=DeleteCases[Table[GraphData[{"CubeConnectedCycle",n},"HosoyaIndex"],{n,3,10}],_Missing|_GraphData]//Quiet

Cycle

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

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

FullSimplify[(2^(-1-n)) ((((-1+(Sqrt[5])))^n)+(((1+(Sqrt[5])))^n)) (1+(E^(I n π))),Mod[n,2]==1]

FullSimplify[(2^(-1-n)) ((((-1+(Sqrt[5])))^n)+(((1+(Sqrt[5])))^n)) (1+(E^(I n π))),Mod[n,2]==0]

Table[(2^(-n)) ((((-1+(Sqrt[5])))^n)+(((1+(Sqrt[5])))^n)),{n,4,10,2}]//FullSimplify

Table[LucasL[n],{n,10}]

Empty

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

FindSequenceFunction[l][n]

FoldedCube

l=DeleteCases[Table[GraphData[{"FoldedCube",n},"HosoyaIndex"],{n,2,10}],_Missing]//Quiet

FindSequenceFunction[l,n-1]

Gear

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

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

Grid (Subscript[P, n])□(Subscript[P, n])

https://oeis.org/A028420

l=DeleteCases[Table[GraphData[{"Grid",{n,n}},"HosoyaIndex"],{n,10}],_Missing]

Length[l]

FindSequenceFunction[l,n]

Grid (Subscript[P, n])□(Subscript[P, n])□(Subscript[P, n])

https://oeis.org/A033535

l=DeleteCases[Table[GraphData[{"Grid",{n,n,n}},"HosoyaIndex"],{n,1,10}],_Missing]

HalvedCube

l=DeleteCases[Table[GraphData[{"HalvedCube",n},"HosoyaIndex"],{n,10}],_Missing]

FindSequenceFunction[l,n]

FindGeneratingFunction[l,x]

FindLinearRecurrence[l]

Hypercube

https://oeis.org/A045310

l=DeleteCases[Table[GraphData[{"Hypercube",n},"HosoyaIndex"],{n,10}],_Missing]

FindSequenceFunction[l,n]

FindGeneratingFunction[l,x]

FindLinearRecurrence[l]

Keller

l=Table[GraphData[{"Keller",n},"HosoyaIndex"],{n,6}]//Quiet

Lattice

l=DeleteCases[Table[GraphData[{"Lattice",{n,n}},"HosoyaIndex"],{n,10}],_Missing]//Quiet

MöbiusLadder

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

FindSequenceFunction[l,n-2]

FindGeneratingFunction[Drop[l,2],x](x^3)//Factor

Series[%,{x,0,20}]

FullSimplify[SeriesCoefficient[-((2 (x^3) (-17-19 x+2 (x^2)+5 (x^3)))/((1+x) (1-3 x-(x^2)+(x^3)))),{x,0,n}],n>2&&n∈Integers]

Table[-(((-1))^n)+((Root[1-#1-3 ((#1)^2)+((#1)^3)&,1])^n)+((Root[1-#1-3 ((#1)^2)+((#1)^3)&,2])^n)+((Root[1-#1-3 ((#1)^2)+((#1)^3)&,3])^n),{n,10}]//RootReduce

Table[-(-1)^n+RootSum[1-#1-3 ((#1)^2)+((#1)^3)&,#^n&],{n,30}]

Mycielski

l=DeleteCases[Table[GraphData[{"Mycielski",n},"HosoyaIndex"],{n,10}],_Missing]

Odd

l=DeleteCases[Table[GraphData[{"Odd",n},"HosoyaIndex"],{n,10}],_Missing]

Pan

https://oeis.org/A006355

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

FindSequenceFunction[l,n-2]//FullSimplify

Table[Fibonacci[n-1]+Fibonacci[n+2],{n,3,20}]

Path

https://oeis.org/A000045

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

f=FindSequenceFunction[l,n]//FullSimplify

PermutationStar

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

Prism

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

l/2

FindSequenceFunction[l,n-2]//FullSimplify

FindGeneratingFunction[Drop[l,2],x](x^3)//Factor

FullSimplify[SeriesCoefficient[-((2 (x^3) (-16-22 x+(x^2)+6 (x^3)))/((1+x) (1-3 x-(x^2)+(x^3)))),{x,0,n}],n>2&&n∈Integers]

Table[(((-1))^n)+RootSum[1-#1-3 ((#1)^2)+((#1)^3)&,((#)^n)&],{n,30}]

Star

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

FindSequenceFunction[l,n]

Table[Piecewise[{{n,Mod[n,2]==0}}],{n,80}]

Sun

https://oeis.org/A192856

l=DeleteCases[Table[GraphData[{"Sun",n},"HosoyaIndex"],{n,3,20}],_Missing]//Quiet

FindSequenceFunction[l,n-2]

Table[Sum[(2*j-1)!!*Binomial[n,2*j],{j,0,n/2}]+2*Sum[n*Binomial[2*n-k-1,k-1]*Sum[(2*j-1)!!*Binomial[n-k,2*j],{j,0,(n-k)/2}]/k,{k,1,n}],{n,3,20}]

Sunlet

https://oeis.org/A002203

Companion Pell numbers (Subscript[Q, n])

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

FindSequenceFunction[l,n-2]//FullSimplify

Table[(((1-(Sqrt[2])))^n)+(((1+(Sqrt[2])))^n),{n,30}]//Expand

Tetrahedral

l=DeleteCases[Table[GraphData[{"Tetrahedral",n},"HosoyaIndex"],{n,6,20}],_Missing|_GraphData]//Quiet

TorusGrid

l=DeleteCases[Table[GraphData[{"TorusGrid",{n,n}},"HosoyaIndex"],{n,3,10}],_Missing]//Quiet

Transposition

l=DeleteCases[Table[GraphData[{"Transposition",n},"HosoyaIndex"],{n,6}],_Missing]//Quiet

Triangular

l=DeleteCases[Table[GraphData[{"Triangular",n},"HosoyaIndex"],{n,2,10}],_Missing]//Quiet

Web

l=DeleteCases[Table[GraphData[{"Web",n},"HosoyaIndex"],{n,3,20}],_Missing]//Quiet

FindLinearRecurrence[l,4]

LinearRecurrence[{3,7,1,-1},{93,439,1988,9107},20]

LinearRecurrence[{3,7,1,-1},{93,439,1988,9107},{-2,1}]

LinearRecurrence[{3,7,1,-1},{4,3,23,93},20]

LinearRecurrence[{3,7,1,-1},{4,3,23,93},20]

FindSequenceFunction[l,n-2]

Table[SeriesCoefficient[-(23*x^3-20*x^2-160*x-93)*x^3/(x^4-x^3-7*x^2-3*x+1),{x,0,n}],{n,20}]

Wheel

https://oeis.org/A061705

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

Table[(n-1)*Fibonacci[n-1]+LucasL[n-1],{n,4,20}]

Table[n*Fibonacci[n]-(n-2)*Fibonacci[n-2],{n,4,20}]

FindSequenceFunction[l,n-3]

FindLinearRecurrence[l]

LinearRecurrence[{0,6,0,-11,0,6,0,-1},{10,0,36,0,120,0,382,0},{-2,40}]

FindSequenceFunction[l[[1;;All;;2]],n]

FindGeneratingFunction[l[[1;;All;;2]],x]

FindLinearRecurrence[l[[1;;All;;2]]]

LinearRecurrence[{6,-11,6,-1},{10,36,120,382},{0,30}]

RSolve[a[n]==6a[n-1]-11a[n-2]+6a[n-3]-1a[n-4]&&a[1]==10&&a[2]==36&&a[3]==120&&a[4]==382,a[n],n]//FullSimplify

Examples

46

Devillers, J. and Balaban.  Topological Indices and Related Descriptors in Qsar and Qspar,

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

HosoyaIndex[g]//TraditionalForm

EdgeAdd[VertexAdd[GraphData[{"Pan",4}],{6,7,8}],{5\[UndirectedEdge]6,2\[UndirectedEdge]7,2\[UndirectedEdge]8}]

RecognizeGraph[%]

86

Devillers, J. and Balaban.  Topological Indices and Related Descriptors in Qsar and Qspar, p. 105

ShowLabeledGraph[g=AddEdges[AddVertex[Cycle[3],{2,0}],{{3,4}}]]

HosoyaIndex[g]

GraphData[{"Pan",3}]

GraphData[{"Pan",3},"HosoyaIndex"]

GraphData[{"Pan",3},"ZIndex"]

Paths

Hosoya 1971, Table 1a

GraphicsGrid[{GraphData[{"Path",#}]&/@Range[5]}]

Table[HosoyaIndex[Path[n]],{n,6}]

Table[HosoyaIndex0[Path[n]],{n,6}]

Table[HosoyaIndex1[Path[n]],{n,6}]

GraphData["Methane"]

Through[{HosoyaIndex,HosoyaIndex0,HosoyaIndex1}[Graph["Methane"]]]

Rotate[GraphData["CrossGraph"],π/2]

Through[{HosoyaIndex,HosoyaIndex0,HosoyaIndex1}[Graph["CrossGraph"]]]

Co-Hosoya

List

Table[Total[Length/@Select[Split[Sort[HosoyaIndex/@ConnectedGraphs[n,"Format"->"V7"]]],Length[#]>1&]],{n,8}]//Timing

Table[Total[Length/@Select[Split[Sort[HosoyaIndex/@ConnectedGraphs[n,"Format"->"V7"]]],Length[#]>1&]],{n,9}]//Timing

FindSequenceFunction[l,n-3]

FindGeneratingFunction[l,x]

FindLinearRecurrence[l]

3 Connected

{#[[1]],Length[#]}&/@Select[Split[Sort[HosoyaIndex/@ConnectedGraphs[3,"Format"->"V7"]]],Length[#]>1&]

4 All

GraphicsGrid[Partition[Graphs[4],5,5,{1,1},{}],Dividers->All]

Partition[HosoyaIndex/@Graphs[4,"Format"->"V7"],5,5,{1,1},{}]

4 Connected

{#[[1]],Length[#]}&/@Select[Split[Sort[HosoyaIndex/@ConnectedGraphs[4,"Format"->"V7"]]],Length[#]>1&]

{#[[1,1]],#[[All,2]]}&/@Select[SplitBy[SortBy[{HosoyaIndex[#],RecognizeGraph[#]}&/@ConnectedGraphs[4,"Format"->"V7"],First],First],Length[#]>1&]

5 All

GraphicsGrid[Partition[Graphs[5],8,8,{1,1},{}],Dividers->All]

Partition[HosoyaIndex/@Graphs[5,"Format"->"V7"],8,8,{1,1},{}]//Column

5 Connected

{#[[1]],Length[#]}&/@Select[Split[Sort[HosoyaIndex/@ConnectedGraphs[5,"Format"->"V7"]]],Length[#]>1&]

{#[[1,1]],#[[All,2]]}&/@Select[SplitBy[SortBy[{HosoyaIndex[#],RecognizeGraph[#]}&/@ConnectedGraphs[5,"Format"->"V7"],First],First],Length[#]>1&]//Column

6 Connected

{#[[1]],Length[#]}&/@Select[Split[Sort[HosoyaIndex/@ConnectedGraphs[6,"Format"->"V7"]]],Length[#]>1&]

{#[[1,1]],#[[All,2]]}&/@Select[SplitBy[SortBy[{HosoyaIndex[#],RecognizeGraph[#]}&/@ConnectedGraphs[6,"Format"->"V7"],First],First],Length[#]>1&]//Column