TOPICS
Search

Hosoya Index

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

As proposed by Hosoya (1971), the Hosoya index (also called Z-index) of a graph is defined by

Z=sum_(k=0)^(n)|a_k|
(1)
=sum_(k=0)^(n)b_k,
(2)

where n is the number of vertices of the graph, a_k is the kth coefficient of the matching polynomial, b_k is the kth coefficient of the matching-generating polynomial, and |x| is the absolute value of x. In others words, it is just the number of independent edge sets (i.e., matchings) in a graph.

An alternate definition for the Hosoya index defined by Devillers and Balaban (1999, p. 105) is given by

Z^'=sum_(k=0)^(|_n/2_|)|a_(2k)|,
(3)

where |_n_| denotes the floor function. This definition is identical to Z except for graphs with odd vertex count, in which case it is 0 (making it not terribly useful).

Unless otherwise stated, hydrogen atoms are usually ignored in the computation of such indices as organic chemists usually do when they write a benzene ring as a hexagon (Devillers and Balaban 1999, p. 25).

The following table summarizes values of the Hosoya index for various special classes of graphs.

graph classOEISZ(G_1), Z(G_2), ...
Andrásfai graphA0000002, 11, 106, 1475, 27514, 651815, 18926340, 655968971, ...
antiprism graphA192742X, X, 51, 191, 708, 2631, 9775, 36319, 134943, 501380, ...
Apollonian networkA00000010, 99, 38613, ...
cocktail party graph K_(n×2)A0000001, 7, 51, 513, 6345, 93255, 1584555, 30524865, 656843985, ...
complete bipartite graph K_(n,n)A0027202, 7, 34, 209, 1546, ...
complete graph K_nA0000851, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, ...
complete tripartite graph K_(n,n,n)A0000004, 51, 1126, 37201, 1670136, 96502339, ...
crossed prism graphA000000X, 108, 1092, 11208, 115272, ...
crown graphA144085X, X, 18, 108, 780, 6600, 63840, 693840, 8361360, ...
cycle graph C_nA000032X, X, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...
empty graph K^__nA0000121, 1, 1, 1, 1, 1, 1, 1, ...
folded cube graphA0000002, 10, 209, 115536, 85609174977, ...
grid graph P_n square P_nA0284201, 7, 131, 10012, 2810694, 2989126727, 11945257052321, ...
grid graph P_n square P_n square P_nA0335351, 1, 108, 49793133, 17312701462385916505, ...
halved cube graphA0000001, 2, 10, 513, 4281761, ...
hypercube graph Q_nA0453102, 7, 108, 41025, 13803794944, ...
Keller graph G_nA0000001, 115536, ...
Möbius ladder M_nA020877X, X, 34, 106, 344, 1102, 3546, ...
Mycielski graphA0000001, 2, 11, 968, 37270256, ...
odd graph O_nA0000001, 4, 332, 11311777344, ...
pan graphA0063556, 10, 16, 26, 42, 68, 110, 178, 288, 466, ...
path graph P_nA0000451, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
permutation star graph PS_nA0000001, 2, 18, 1157484, ...
prism graph Y_nA102080X, X, 32, 108, 342, 1104, 3544, 11396, 36626, ...
rook graph K_n square K_nA0000001, 7, 370, 270529, 3337807996, ...
star graph S_nA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
sun graphA192856X, X, 27, 100, 393, 1624, 7017, 31558, 147177, ...
sunlet graph C_n circledot K_1A002203X, X, 14, 34, 82, 198, 478, 1154, 2786, 6726, ...
torus grid graph C_n square C_nA000000X, X, 370, 40125, ...
transposition graph G_nA0000001, 2, 34, 161966673, ...
triangular graphA0000001, 4, 51, 2460, 513619, 509709696, ...
web graphA192857X, X, 93, 439, 1988, 9107, 41583, 190047, 868341, 3967828, ...
wheel graph W_nA061705X, X, X, 10, 19, 36, 66, 120, 215, 382, 673, 1178, 2050, 3550, 6121, ...

Closed forms are summarized in the following table, where (p(x))_k denotes the kth polynomial root of p(x), U(a,b,x) is a confluent hypergeometric function of the second kind, L_n is a Lucas number, L_n(x) is a Laguerre polynomial, F_n is a Fibonacci number, and Q_n is a Pell-Lucas number.

graphZ(G_n)
antiprism graphsum_(k=1)^(4)(1+x-3x^2-3x^3+x^4)_k^n
complete graph K_n(-1)^n(-2)^(n/2)U(1/2n,1/2,-1/2)
complete bipartite graph K_(n,n)n!L_n(-1)
cycle graph C_nL_n
empty graph K^__n1
Möbius ladder M_n(-1)^(n+1)+sum_(k=1)^(3)(1-x-3x^2+x^3)_k^n
pan graphF_(n-1)+F_(n+2)
path graph P_n1/2(F_n+L_n)
prism graph Y_n(-1)^n+sum_(k=1)^(3)(x^3-3x^2-x+1)_k^n
star graph S_nn
sunlet graph C_n circledot K_1Q_n
wheel graph W_n(n-1)F_(n-1)+L_(n-1)

See also

Independent Edge Set, Matching, Matching Polynomial, Stability Index

Explore with Wolfram|Alpha

References

Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 27-28 and 105, 1999.Hosoya, H. "A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons." Bull. Chem. Soc. Japan 44, 2332-2339, 1971.Hosoya, H. and Murakami, M. "Topological Index as Applied to pi-Electronic Systems. II. Topological Bond Order." Bull. Chem. Soc. Japan 48, 3512-3517, 1975.Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A000085/M1221, A000045/M0692, A002203, A002720/M1795, A006355, A020877, A025169, A028420, A033535, A045310, A102080, A144085, A192742, A192856, A192857, and A192858 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Hosoya Index

Cite this as:

Weisstein, Eric W. "Hosoya Index." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HosoyaIndex.html

Subject classifications