The Smallest Merrifield-Simmons Index of Trees with Exactly Six Leaves

Abstract

The Merrifield-Simmons index $\sigma (G)$ of a graph $G$ is defined as the number of subsets of the vertex set, in which any two vertices are non-adjacent, i.e., the number of independent vertex sets of $G$. A tree is called an $r$-leaf tree if it contains $r$ vertices with degree one. In this paper, we obtain the smallest Merrifield-Simmons index among all trees with $n$ vertices and exactly six leaves, and characterize the corresponding extremal graph.