World Scientific
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Mon, Jun 21st, 2021 at 1am (EDT)

During this period, the E-commerce and registration of new users may not be available for up to 6 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.


    The computational complexity of the Hosoya index of a given graph is NP-Complete. Let RT(G) be the graph constructed from R(G) by a triangle instead of all vertices of the initial graph G. In this paper, we characterize the Hosoya index of the graph RT(G). To our surprise, it shows that the Hosoya index of RT(G) is thoroughly given by the order and degrees of all the vertices of the initial graph G.


    • 1. Z. Zhang and F. Comellas , Farey graphs as models for complex networks, Theor. Comput. Sci. 412(8–10) (2011) 865–875. Crossref, ISIGoogle Scholar
    • 2. Z. Zhang, L. Rong and S. Zhou , A general geometric growth model for pseudofractal scale-free web, Physica A 377(1) (2007) 329–339. Crossref, ISIGoogle Scholar
    • 3. J. A. Bondy and U. S. R. Murty , Graph Theory with Applications (Macmillan, New York, 1976). CrossrefGoogle Scholar
    • 4. S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes , Pseudofractal scale-free web, Phys. Rev. E 65(6) (2002) 066122. Crossref, ISIGoogle Scholar
    • 5. W. Sun, M. Sun, J. Guan and Q. Jia , Robustness of coherence in noisy scale-free networks and applications to identification of influential spreaders, IEEE Trans. Circuits Syst. II (2019), CrossrefGoogle Scholar
    • 6. W. Sun, Q. Ding, J. Zhang and F. Chen , Coherence in a family of tree networks with an application of Laplacian spectrum, Chaos 24(4) (2014) 043112. Crossref, ISIGoogle Scholar
    • 7. M. Hong, W. Sun, S. Liu and T. Xuan , Coherence analysis and Laplacian energy of recursive trees with controlled initial states, Front. Inf. Technol. Electron. Eng. (2019), CrossrefGoogle Scholar
    • 8. J. B. Liu, S. Wang, C. Wang and S. Hayat , Further results on computation of topological indices of certain networks, IET Control Theory Appl. 11(13) (2017) 2065–2071. Crossref, ISIGoogle Scholar
    • 9. L. Malozemov and A. Teplyaev , Pure point spectrum of the Laplacians on fractal graphs, J. Funct. Anal. 129(2) (1995) 390–405. Crossref, ISIGoogle Scholar
    • 10. W. Yan and Y. N. Yeh , On the number of matchings of graphs formed by a graph operation, Sci. China A 49 (2006) 1383–1391. Crossref, ISIGoogle Scholar
    • 11. H. Hosoya , Topological index: A newly proposed quantity characterizing the topological nature of structural isomers of haturated hydrocarbons, Bull. Chem. Soc. Jpn. 44 (1971) 2332–2339. Crossref, ISIGoogle Scholar
    • 12. X. Chen, J. Zhang and W. Sun , On the Hosoya index of a family of deterministic recursive trees, Physica A 465 (2017) 449–453. Crossref, ISIGoogle Scholar
    • 13. I. Gutman and O. E. Polansky , Mathematical Concepts Organic Chemistry (Springer, Berlin, 1986). CrossrefGoogle Scholar
    • 14. D. Cvetković, M. Doob and H. Sachs , Spectra of Graph Theory and Applications (Academic Press, New York, 1980). Google Scholar
    • 15. J. B. Liu, X. F. Pan and F. T. Hu , The Laplacian polynomial of graphs derived from regular graphs and applications, Ars Combin. 126 (2016) 289–300. ISIGoogle Scholar
    • 16. M. Jerrum , Two-dimensional monomer-dimer systems are computationally intractable, J. Stat. Phys. 48 (1987) 121–134. Crossref, ISIGoogle Scholar
    • 17. C. Xiao, H. Chen and A. M. Raigorodskii , A connection between the Kekulé structures of pentagonal chains and the Hosoya index of caterpillar trees, Discrete Appl. Math. 232 (2017) 230–234. Crossref, ISIGoogle Scholar
    • 18. Z. Zhu, C. Yuan, E. O. D. Andriantiana and S. Wagner , Graphs with maximal Hosoya index and minimal Merrifield–Simmons index, Discrete Math. 329 (2014) 77–87. Crossref, ISIGoogle Scholar
    • 19. S. Li, X. Li and W. Jing , On the extremal Merrifield–Simmons index and Hosoya index of quasi-tree graphs, Discrete Appl. Math. 157 (2009) 2877–2885. Crossref, ISIGoogle Scholar
    • 20. 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. Crossref, ISIGoogle Scholar
    • 21. K. Xu, J. Li and L. Zhong , The Hosoya indices and Merrifield–Simmons indices of graphs with connectivity at most k, Appl. Math. Lett. 25 (2012) 476–480. Crossref, ISIGoogle Scholar
    • 22. H. Hua , Minimizing a class of unicyclic graphs by means of Hosoya index, Math. Comput. Model. 48 (2008) 940–948. CrossrefGoogle Scholar
    • 23. H. Deng , The largest Hosoya index of (n,n + 1)-graphs, Comput. Math. Appl. 56 (2008) 2499–2506. Crossref, ISIGoogle Scholar
    • 24. Z. Shao, P. Wu, Y. Gao, I. Gutman and X. Zhang , On the maximum ABC index of graphs without pendent vertices, Appl. Math. Comput. 315 (2017) 298–312. ISIGoogle Scholar
    • 25. F. Zhang , The Schur Complement and its Applications (Springer-Verlag, New York, 2005). CrossrefGoogle Scholar
    • 26. C. D. Godsil , Algebraic Combinatorics (Chapman and Hall, New York, 1993). Google Scholar
    • 27. E. J. Farrell and S. A. Wahid , D-graphs, I. An introduction to graphs whose matching polynomials are determinants of matrices, Bull. Inst. Combin. Appl. 15 (1995) 81–86. Google Scholar
    • 28. W. Yan, Y. N. Yeh and F. J. Zhang , On the matching polynomials of graphs with small number of cycles of even length, Int. J. Quantum Chem. 105 (2005) 124–130. Crossref, ISIGoogle Scholar
    Published: December 31, 2019
    Remember to check out the Most Cited Articles!

    Check out New Titles in Materials Science and Nanotechnology
    Includes authors Michael Frame, Nathan Cohen, Susie Vrobel and more