Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418576 | Discrete Applied Mathematics | 2011 | 10 Pages |
Abstract
The Merrifield–Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Denote by G(n,k)G(n,k) the set of connected graphs with nn vertices and kk cut vertices. In this paper, we characterize the graphs with the maximum and minimum Merrifield–Simmons index, respectively, among all graphs in G(n,k)G(n,k) for all possible kk values.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hongbo Hua, Shenggui Zhang,