**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**30172

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