Hosoya Index

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

			(1)
			(2)

where  is the number of vertices of the graph,  is the th coefficient of the matching polynomial,  is the th coefficient of the matching-generating polynomial, and  is the absolute value of . 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

(3)

where  denotes the floor function. This definition is identical to  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 class	OEIS	, , ...
Andrásfai graph	A000000	2, 11, 106, 1475, 27514, 651815, 18926340, 655968971, ...
antiprism graph	A192742	X, X, 51, 191, 708, 2631, 9775, 36319, 134943, 501380, ...
Apollonian network	A000000	10, 99, 38613, ...
cocktail party graph	A000000	1, 7, 51, 513, 6345, 93255, 1584555, 30524865, 656843985, ...
complete bipartite graph	A002720	2, 7, 34, 209, 1546, ...
complete graph	A000085	1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, ...
complete tripartite graph	A000000	4, 51, 1126, 37201, 1670136, 96502339, ...
crossed prism graph	A000000	X, 108, 1092, 11208, 115272, ...
crown graph	A144085	X, X, 18, 108, 780, 6600, 63840, 693840, 8361360, ...
cycle graph	A000032	X, X, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...
empty graph	A000012	1, 1, 1, 1, 1, 1, 1, 1, ...
folded cube graph	A000000	2, 10, 209, 115536, 85609174977, ...
grid graph	A028420	1, 7, 131, 10012, 2810694, 2989126727, 11945257052321, ...
grid graph	A033535	1, 1, 108, 49793133, 17312701462385916505, ...
halved cube graph	A000000	1, 2, 10, 513, 4281761, ...
hypercube graph	A045310	2, 7, 108, 41025, 13803794944, ...
Keller graph	A000000	1, 115536, ...
Möbius ladder	A020877	X, X, 34, 106, 344, 1102, 3546, ...
Mycielski graph	A000000	1, 2, 11, 968, 37270256, ...
odd graph	A000000	1, 4, 332, 11311777344, ...
pan graph	A006355	6, 10, 16, 26, 42, 68, 110, 178, 288, 466, ...
path graph	A000045	1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
permutation star graph	A000000	1, 2, 18, 1157484, ...
prism graph	A102080	X, X, 32, 108, 342, 1104, 3544, 11396, 36626, ...
rook graph	A000000	1, 7, 370, 270529, 3337807996, ...
star graph	A000027	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
sun graph	A192856	X, X, 27, 100, 393, 1624, 7017, 31558, 147177, ...
sunlet graph	A002203	X, X, 14, 34, 82, 198, 478, 1154, 2786, 6726, ...
torus grid graph	A000000	X, X, 370, 40125, ...
transposition graph	A000000	1, 2, 34, 161966673, ...
triangular graph	A000000	1, 4, 51, 2460, 513619, 509709696, ...
web graph	A192857	X, X, 93, 439, 1988, 9107, 41583, 190047, 868341, 3967828, ...
wheel graph	A061705	X, X, X, 10, 19, 36, 66, 120, 215, 382, 673, 1178, 2050, 3550, 6121, ...

Closed forms are summarized in the following table, where  denotes the th polynomial root of ,  is a confluent hypergeometric function of the second kind,  is a Lucas number,  is a Laguerre polynomial,  is a Fibonacci number, and  is a Pell-Lucas number.

graph
antiprism graph
complete graph
complete bipartite graph
cycle graph
empty graph	1
Möbius ladder
pan graph
path graph
prism graph
star graph
sunlet graph
wheel graph

---

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 -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."

اخر الاخبار

اخبار العتبة العباسية المقدسة

أكثر من 10,000 مستفيدة من خدمات معهد القرآن الكريم النسوي في زيارة الأربعين

بالأرقام.. قسم العلاقات العامة يحصي خدماته في زيارة الأربعين

قسم المضيف يعلن تقديم أكثر من 7 ملايين وجبة طعام لزائري الأربعين

قسم الاتصالات: أكثر من 16 ألف حالة فقدان أُعيدت لذويها بجهود العتبتين المقدستين

المزيد

الآخبار الصحية

"ساعة الذئب" تؤرق الملايين.. حل علمي ينقذ نومك

يخفف الألم.. معجون أسنان مصنوع من الشعر ؟!

كوابيسك ليست عشوائية.. ماذا تحاول أن تخبرك؟

5 مخاطر غير متوقعة لتناول البروتين بكثرة

المزيد

الآخبار التكنلوجية

أندرويد 16 على الأبواب..هاتفك سيصبح وكيلك الذكي !

"غوغل" مهددة ببيع متصفحها الشهير "كروم".. من المشتري؟

"ناسا" و"غوغل" تطوران مساعدا طبيا ذكيا لمرافقة رواد الفضاء

هل تشغيل تكييف السيارة على "الحد الأقصى" ضار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength