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

作者：Hua Hongbo^*; Xu Xinli; Wang Hongzhuan

来源：Filomat, 2014, 28(3): 451-461.

DOI：10.2298/FIL1403451H

• independent set
• Merrifield-Simmons index
• unicyclic graph
• cut vertices
• upper bound
• extremal graph

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.

• 出版日期2014
• 单位南京大学; 淮阴工学院