Unicyclic Graphs With Given Number of Cut Vertices and the Maximal Merrifield--Simmons Index


Hongbo Hua, Xinli Xu, Hongzhuan Wang




The Merrifield--Simmons index of a graph $G$, denoted by $i(G)$, is defined to be the total number of independent sets in $G$, including the empty set. A connected graph is called a unicyclic graph, if it possesses equal number of vertices and edges. In this paper, we characterize the maximal unicyclic graph w.r.t. $i(G)$ within all unicyclic graphs with given order and number of cut vertices. As a consequence, we determine the connected graph with at least one cycle, given number of cut vertices and the maximal Merrifield--Simmons index.