×

The Hosoya index of graphs formed by a fractal graph. (English) Zbl 1434.05039

Summary: The computational complexity of the Hosoya index of a given graph is NP-Complete. Let \(R T(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 \(R T(G)\). To our surprise, it shows that the Hosoya index of \(R T(G)\) is thoroughly given by the order and degrees of all the vertices of the initial graph \(G\).

MSC:

05C09 Graphical indices (Wiener index, Zagreb index, Randić index, etc.)
28A80 Fractals
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zhang, Z. and Comellas, F., Farey graphs as models for complex networks, Theor. Comput. Sci.412(8-10) (2011) 865-875. · Zbl 1206.68245
[2] Zhang, Z., Rong, L. and Zhou, S., A general geometric growth model for pseudofractal scale-free web, Physica A377(1) (2007) 329-339.
[3] Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications (Macmillan, New York, 1976). · Zbl 1226.05083
[4] Dorogovtsev, S. N., Goltsev, A. V. and Mendes, J. F. F., Pseudofractal scale-free web, Phys. Rev. E65(6) (2002) 066122.
[5] Sun, W., Sun, M., Guan, J. and Jia, Q., 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.
[6] Sun, W., Ding, Q., Zhang, J. and Chen, F., Coherence in a family of tree networks with an application of Laplacian spectrum, Chaos24(4) (2014) 043112. · Zbl 1361.34027
[7] Hong, M., Sun, W., Liu, S. and Xuan, T., 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.
[8] Liu, J. B., Wang, S., Wang, C. and Hayat, S., Further results on computation of topological indices of certain networks, IET Control Theory Appl.11(13) (2017) 2065-2071.
[9] Malozemov, L. and Teplyaev, A., Pure point spectrum of the Laplacians on fractal graphs, J. Funct. Anal.129(2) (1995) 390-405. · Zbl 0822.05045
[10] Yan, W. and Yeh, Y. N., On the number of matchings of graphs formed by a graph operation, Sci. China A49 (2006) 1383-1391. · Zbl 1110.05085
[11] Hosoya, H., Topological index: A newly proposed quantity characterizing the topological nature of structural isomers of haturated hydrocarbons, Bull. Chem. Soc. Jpn.44 (1971) 2332-2339.
[12] Chen, X., Zhang, J. and Sun, W., On the Hosoya index of a family of deterministic recursive trees, Physica A465 (2017) 449-453. · Zbl 1400.05181
[13] Gutman, I. and Polansky, O. E., Mathematical Concepts Organic Chemistry (Springer, Berlin, 1986). · Zbl 0657.92024
[14] Cvetković, D., Doob, M. and Sachs, H., Spectra of Graph Theory and Applications (Academic Press, New York, 1980). · Zbl 0458.05042
[15] Liu, J. B., Pan, X. F. and Hu, F. T., The Laplacian polynomial of graphs derived from regular graphs and applications, Ars Combin.126 (2016) 289-300. · Zbl 1413.05182
[16] Jerrum, M., Two-dimensional monomer-dimer systems are computationally intractable, J. Stat. Phys.48 (1987) 121-134.
[17] Xiao, C., Chen, H. and Raigorodskii, A. M., A connection between the Kekulé structures of pentagonal chains and the Hosoya index of caterpillar trees, Discrete Appl. Math.232 (2017) 230-234. · Zbl 1372.05037
[18] Zhu, Z., Yuan, C., Andriantiana, E. O. D. and Wagner, S., Graphs with maximal Hosoya index and minimal Merrifield-Simmons index, Discrete Math.329 (2014) 77-87. · Zbl 1295.05190
[19] Li, S., Li, X. and Jing, W., On the extremal Merrifield-Simmons index and Hosoya index of quasi-tree graphs, Discrete Appl. Math.157 (2009) 2877-2885. · Zbl 1209.05173
[20] Xu, K., On the Hosoya index and the Merrifield-Simmons index of graphs with a given clique number, Appl. Math. Lett.23 (2010) 395-398. · Zbl 1218.05073
[21] Xu, K., Li, J. and Zhong, L., The Hosoya indices and Merrifield-Simmons indices of graphs with connectivity at most \(k\), Appl. Math. Lett.25 (2012) 476-480. · Zbl 1243.05125
[22] Hua, H., Minimizing a class of unicyclic graphs by means of Hosoya index, Math. Comput. Model.48 (2008) 940-948. · Zbl 1156.05328
[23] Deng, H., The largest Hosoya index of \((n, n + 1)\)-graphs, Comput. Math. Appl.56 (2008) 2499-2506. · Zbl 1165.05321
[24] Shao, Z., Wu, P., Gao, Y., Gutman, I. and Zhang, X., On the maximum \(A B C\) index of graphs without pendent vertices, Appl. Math. Comput.315 (2017) 298-312. · Zbl 1426.05082
[25] Zhang, F., The Schur Complement and its Applications (Springer-Verlag, New York, 2005). · Zbl 1075.15002
[26] Godsil, C. D., Algebraic Combinatorics (Chapman and Hall, New York, 1993). · Zbl 0784.05001
[27] Farrell, E. J. and Wahid, S. A., \(D\)-graphs, I. An introduction to graphs whose matching polynomials are determinants of matrices, Bull. Inst. Combin. Appl.15 (1995) 81-86. · Zbl 0854.05072
[28] Yan, W., Yeh, Y. N. and Zhang, F. J., On the matching polynomials of graphs with small number of cycles of even length, Int. J. Quantum Chem.105 (2005) 124-130.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.