• Search

×
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 www.worldscientific.com.

### 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.
ArticleNo Access

# THE HOSOYA INDEX OF GRAPHS FORMED BY A FRACTAL GRAPH

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

## References

• 1. Z. Zhang and F. Comellas , Farey graphs as models for complex networks, Theor. Comput. Sci. 412(8–10) (2011) 865–875. Crossref, ISI
• 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, ISI
• 3. J. A. Bondy and U. S. R. Murty , Graph Theory with Applications (Macmillan, New York, 1976). Crossref
• 4. S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes , Pseudofractal scale-free web, Phys. Rev. E 65(6) (2002) 066122. Crossref, ISI
• 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), https://doi.org/10.1109/TCSII.2019.2929139. Crossref
• 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, ISI
• 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), https://doi.org/10.1631/FITEE.1900133. Crossref
• 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, ISI
• 9. L. Malozemov and A. Teplyaev , Pure point spectrum of the Laplacians on fractal graphs, J. Funct. Anal. 129(2) (1995) 390–405. Crossref, ISI
• 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, ISI
• 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, ISI
• 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, ISI
• 13. I. Gutman and O. E. Polansky , Mathematical Concepts Organic Chemistry (Springer, Berlin, 1986). Crossref
• 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. ISI
• 16. M. Jerrum , Two-dimensional monomer-dimer systems are computationally intractable, J. Stat. Phys. 48 (1987) 121–134. Crossref, ISI
• 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, ISI
• 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, ISI
• 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, ISI
• 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, ISI
• 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, ISI
• 22. H. Hua , Minimizing a class of unicyclic graphs by means of Hosoya index, Math. Comput. Model. 48 (2008) 940–948. Crossref
• 23. H. Deng , The largest Hosoya index of $(n,n + 1)$-graphs, Comput. Math. Appl. 56 (2008) 2499–2506. Crossref, ISI
• 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. ISI
• 25. F. Zhang , The Schur Complement and its Applications (Springer-Verlag, New York, 2005). Crossref
• 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, ISI
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

"