×

zbMATH — the first resource for mathematics

The Merrifield-Simmons index and Hosoya index of \(C(n, k, \lambda)\) graphs. (English) Zbl 1255.05133
Summary: The Merrifield-Simmons index \(i(G)\) of a graph \(G\) is defined as the number of subsets of the vertex set, in which any two vertices are nonadjacent, that is, the number of independent vertex sets of \(G\). The Hosoya index \(z(G)\) of a graph \(G\) is defined as the total number of independent edge subsets, that is, the total number of its matchings. By \(C(n,k,\lambda)\) we denote the set of graphs with \(n\) vertices, \(k\) cycles, the length of every cycle is \(\lambda\), and all the edges not on the cycles are pendant edges which are attached to the same vertex. In this paper, we investigate the Merrifield-Simmons index \(i(G)\) and the Hosoya index \(z(G)\) for a graph \(G\) in \(C(n,k,\lambda)\).
MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. Diestel, Graph Theory, vol. 173 of Graduate Texts in Mathematics, Springer, New York, NY, USA, 2nd edition, 2000. · Zbl 0974.46031 · doi:10.1006/jmaa.2000.7071
[2] R. E. Merrifield and H. E. Simmons, Topological Methods in Chemistry, John Wiley & Sons, New York, NY, USA, 1989.
[3] H. Hosoya, “Topological index, a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons,” Bulletin of the Chemical Society of Japan, vol. 44, pp. 2322-2339, 1971.
[4] H. Deng and S. Chen, “The extremal unicyclic graphs with respect to Hosoya index and Merrifield-Simmons index,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 59, no. 1, pp. 171-190, 2008. · Zbl 1141.05049
[5] M. Fischermann, I. Gutman, A. Hoffmann, D. Rautenbach, D. Vidovic, and L. and Volkmann, “Extremal chemical trees,” Zeitschrift für Naturforschung Section B-A Journal of Chemical Sciences, vol. 57, pp. 49-52, 2002.
[6] M. Fischermann, L. Volkmann, and D. Rautenbach, “A note on the number of matchings and independent sets in trees,” Discrete Applied Mathematics, vol. 145, no. 3, pp. 483-489, 2005. · Zbl 1056.05035 · doi:10.1016/j.dam.2004.07.001
[7] I. Gutman, “Extremal hexagonal chains,” Journal of Mathematical Chemistry, vol. 12, no. 1-4, pp. 197-210, 1993. · doi:10.1007/BF01164635
[8] I. Gutman and F. J. Zhang, “On the ordering of graphs with respect to their matching numbers,” Discrete Applied Mathematics, vol. 15, no. 1, pp. 25-33, 1986. · Zbl 0646.05049 · doi:10.1016/0166-218X(86)90015-6
[9] Y. Hou, “On acyclic systems with minimal Hosoya index,” Discrete Applied Mathematics, vol. 119, no. 3, pp. 251-257, 2002. · Zbl 0999.05020 · doi:10.1016/S0166-218X(01)00306-7
[10] S. G. Wagner, “Extremal trees with respect to Hosoya index and Merrifield-Simmons index,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 57, no. 1, pp. 221-233, 2007. · Zbl 1150.05034
[11] I. Gutman and O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin, Germany, 1986. · Zbl 0657.92024 · doi:10.1007/978-3-642-70982-1
[12] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier, New York, NY, USA, 1976. · Zbl 1226.05083
[13] H. Deng, “The smallest Merrifield-Simmons index of (n,n+1)-graphs,” Mathematical and Computer Modelling, vol. 49, no. 1-2, pp. 320-326, 2009. · Zbl 1165.05337 · doi:10.1016/j.mcm.2008.06.009
[14] H. Deng, “The largest Hosoya index of (n,n+1)-graphs,” Computers & Mathematics with Applications, vol. 56, no. 10, pp. 2499-2506, 2008. · Zbl 1165.05321 · doi:10.1016/j.camwa.2008.05.020
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.