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

اخر الاخبار

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

جامعة الكفيل تنظم مناظرة علمية لعدد من طالبات المدارس الإعدادية

العتبة العباسية المقدسة توضّح تعليمات التسجيل في حفل تخرج دفعة بنات الكفيل العاشرة

قسم الشؤون الفكرية يقيم خيمة ثقافية ضمن برنامج الطالب الفعال في ذي قار

من بين أكثر من (5000) صورة مصوّر المجمَع العلمي يحصد المرتبة الأولى في مسابقة مهر محرم الدولية

المزيد

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

تقرير يكشف علاقة لون الموز بفوائده الصحية

كيف يعزز الزعفران مزاجك ويحمي قلبك ويساعدك على خفض وزنك

خبراء: هذه الفواكه والخضراوات الأكثر تلوثا بالمبيدات

وجبة خفيفة يوميا.. تؤدي إلى قوة الذاكرة لاحقا

المزيد

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

الأرصفة الشمسية.. ابتكار يخفض الانبعاثات 98%

إبهار الضوء أثناء القيادة: المخاطر والنصائح للتعامل معه

شركات أميركية تتنافس لحجب الشمس.. وخبراء يحذرون

قرار أميركي مفاجئ بشأن "تجارب القردة"

المزيد

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

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