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.