Hosoya index and Fibonacci numbers

Document Type: Original Article


Department of Mathematics, Yazd University, 89195-741, Yazd, Iran


Let G =(V ,E) be a simple graph. The Hosoya index Z(G) of G is defined as the total number of edge independent sets of G . Fibonacci numbers are terms of the sequence defined in a quite simple recursive fashion. In this paper, we investigate the relationships between Hosoya index and Fibonacci numbers. Also we consider Fibonacci cubes and study some of its parameters which is related to Fibonacci numbers.

Graphical Abstract

Hosoya index and Fibonacci numbers


1. O. Chan, I. Gutman, T.K. Lam and R, Merris, Algebraic connections between topological indices, J. Chem. Inform. Comput. Sci. 38 (1998), 62-65.
2. B. Cong, S. Zheng and S. Sharma, On simulations of linear arrays, rings and 2nd meshes on Fibonacci cube networks. In Proceedings of the 7th International Parallel Processing Symphosium, (1993), 747-751.
3. R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math, 4 (1970), 322-324.
4. I. Gutman, On the Hosoya index of very large molecules, MATCH Commum. Math. Comput. Chem. 23 (1988), 95–103.
5. I. Gutman and O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin, (1986).
6. H. Hosoya, Topological index: a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn. 44 (1971), 2332-2339.
7. W.-J. Hsu. Fibonacci cubes—a new interconnection technology. IEEE Trans. Parallel Distrib. Syst., 4(1) (1993), 3-12.
8. W.-J. Hsu, C. V. Page, and J.-S. Liu. Fibonacci cubes—a class of self-similar graphs. Fibonacci Quart., 31(1) (1993), 65–72.
9. H. Hua, Hosoya index of unicyclic graphs with prescribed pendent vertices, J. Math. Chem. 43 (2008), 831–844.
10. S. Klavzar and P. Zigert, Fibonacci cubes are the resonance graphs of Fibonaccenes, Fibonacci Quart. 43 (2005), 269-276.
11. S. Klavzar and M. Mollard, Wiener index and Hosoya polynomial of Fibonacci and Lucas cubes, avvailable at http://hal.archives-ouvertes.fr/hal-00624188/fr/
12. S. Klavzar and M. Mollard.Wiener index and Hosoya polynomial of Fibonacci and Lucas cubes. To appear in MATCH Commun. Math. Comput. Chem., (2012).
13. S. Li and Z. Zhu, The number of independent sets in unicyclic graphs with a given diameter, Discrete Appl. Math. 157 (2009), 1387–1395.
14. D. A. Pike and Y. Zou. The domination number of Fibonacci cubes. To appear in J. Combin. Math. Combin. Comput.
15. S. Wagner, Extemal trees with respect to Hosoya index and Merrifield-Simmons index, MATCH Commun. Math. Comput. Chem. 57 (2007), 221-233.
16. K. Xu, On the Hosoya index and the Merrifield-Simmons index of graphs with a given clique number, Appl. Math. Lett. 23 (2010), 395–398.
17. H. Zhang, P. C. B. Lam, and W. C. Shiu. Resonance graphs and a binary coding for the 1-factors of benzenoid systems. SIAM J. Discrete Math., 22(3) (2008), 971–984.
18. H. Zhang and F. Zhang. Plane elementary bipartite graphs. Discrete Appl. Math., 105(1-3) (2000), 291–311.