A Note on the Merrifield-Simmons Index of Connected Graphs

Abstract

The Merrifield-Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Recently, Heuberger and Wagner [Maximizing the number of independent subsets over trees with bounded degree, J. Graph Theory, $58(2008)49-68$] investigated the problem of determining the trees with the maximum Merrifield-Simmons index among trees of restricted maximum degree. In this note, we consider the problem of determining the graphs with the maximum Merrifield-Simmons index among connected graphs of restricted minimum degree. Let ${\mathcal{G}}_{\delta }(n)$ denote the set of connected graphs of $n$ vertices and minimum degree $\delta$. We first conjecture that among all graphs in ${\mathcal{G}}_{\delta }(n)$, $n\ge 2\delta$, the graphs with the maximum Merrifield-Simmons index are isomorphic to $K_{\delta ,n-\delta }$ or $C_5$. Then we affirm this conjecture for the case of $\delta =1,2,3$.