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

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.





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.