The Extremal Graph with the Largest Merrifield-Simmons Index of (n, n + 2)-graphs

Authors: M. S. Haghighat, A. Dolati, M. Tabari, E. Mohseni

Abstract:

The Merrifield-Simmons index of a graph G is defined as the total number of its independent sets. A (n, n + 2)-graph is a connected simple graph with n vertices and n + 2 edges. In this paper we characterize the (n, n+2)-graph with the largest Merrifield- Simmons index. We show that its Merrifield-Simmons index i.e. the upper bound of the Merrifield-Simmons index of the (n, n+2)-graphs is 9 × 2n-5 +1 for n ≥ 5.

Keywords: Merrifield-Simmons index, (n, n+2)-graph.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1083357

References:

[1] H. Deng, S. Chen, "The extremal unicyclic graphs with respect to Hosoya index and Merrifield-Simmons index", MATCH Commun. Math. Comput. Chem., vol. 59, pp. 171-190, 2008.
[2] H. Deng, S. Chen, J. Zhang, "The Merrifield-Simmons index in (n, n+ 1)-graphs", J. Math. Chem., vol. 43, pp. 75-91, 2008.
[3] A. Dolati, M. Haghighat, S. Golalizadeh, M. Safari, "The Smallest Hosoya Index of Connected Tricyclic Graphs", MATCH Commun. Math. Comput. Chem., vol. 65, pp. 57-70, 2011.
[4] I. Gutman, "Acyclic systems with extremal Huckel ¤Ç-electron", Theor. Chim. Acta, vol. 45, pp. 79-87, 1977.
[5] I. Gutman, O. E. Polansky, "Mathematical Concepts in Organic Chemistry", Springer, Berlin, 1986.
[6] X. Li, Z. Li, L. Wang, "The invers problems for some topological indices in combinatorial chemistry", J. Comput. Boil., vol. 54, pp. 147-55, 2003.
[7] X. Li, H. Zhao, I. Gutman, "On the Merrifield-Simmons index of trees", MATCH commun. Comput. Chem., vol. 54 (2), pp. 389-402, 2005.
[8] R. E. Merrifield, H. E. Simmons, "Topological Methods in Chemistry", Wiley, New York, 1989.
[9] A. S. Pedersen, P. D. Vestergaard, "The number of independent sets in unicyclic graphs", Discrete Appl. Math., vol. 152, pp. 246-256, 2005.
[10] H. Prodinger, R. F. Tichy, "Fibinacci numbers of graphs", Fibinacci Quart, vol. 20, pp. 16-21, 1982.
[11] R. Todeschini, V. Consonni, " Handbook of Molecular Descriptors", Wiley-VCH, Weinheim, 2000.