TOPICS
Search

Hosoya Index

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Hosoya index (also called Z-index) of a graph, as proposed by Hosoya (1971), 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 coefficient of x^k in the matching polynomial, b_k is the coefficient of x^k in the matching-generating polynomial, and |x| is the absolute value of x. In other words, it is just the number of independent edge sets (i.e., matchings) in a graph.

Equivalently, writing the matching polynomial with descending-degree coefficients,

mu(x)=sum_(j=0)^na^~_jx^(n-j),
(3)

gives

Z=sum_(k=0)^(|_n/2_|)|a^~_(2k)|,
(4)

where |_x_| denotes the floor function. This is the same index for both odd and even vertex count, with a^~_j=a_(n-j).

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. Unless stated otherwise, each parameter starts at 1. The folded cube and triangular graph rows start at 2. An X indicates that the family in that row is not defined for the corresponding parameter value.

graph classOEISHosoya indices
Andrásfai graph2, 11, 106, 1475, 27514, 651815, 18926340, 655968971, ...
antiprism graphA192742X, X, 51, 191, 708, 2631, 9775, 36319, 134943, 501380, ...
Apollonian network10, 99, 38613, ...
cocktail party graph K_(n×2)1, 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)4, 51, 1126, 37201, 1670136, 96502339, ...
crossed prism graph with even parameter 2nX, 108, 1092, 11208, 115272, ...
crown graphA1440851, 4, 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 graph2, 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, 108, 49793133, 17312701462385916505, ...
halved cube graph1, 2, 10, 513, 4281761, ...
hypercube graph Q_nA0453102, 7, 108, 41025, 13803794944, ...
Keller graph G_n1, 115536, ...
Möbius ladder M_nA020877X, X, 34, 106, 344, 1102, 3546, ...
Mycielski graph1, 2, 11, 968, 37270256, ...
odd graph O_n1, 4, 332, 11311777344, ...
pan graphA006355X, X, 6, 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_n1, 2, 18, 1157484, ...
prism graph Y_nA102080X, X, 32, 108, 342, 1104, 3544, 11396, 36626, ...
rook graph K_n square K_n1, 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_nX, X, 370, 41025, ...
transposition graph G_n1, 2, 34, 161966673, ...
triangular graph1, 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

WolframAlpha

More things to try:

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, A000032, A000045/M0692, A000085/M1221, A002203, A002720/M1795, A006355, A020877, A025169, A028420, A033535, A045310, A061705, 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 Resource. https://mathworld.wolfram.com/HosoyaIndex.html

Subject classifications