Comparison between Merrifield-Simmons Index and Wiener Index of Graphs

Abstract

The Merrifield-Simmons index σ is the total number of independent vertex sets (including the empty set) of the graph G. The Wiener index W is the sum of distances in all unordered pairs of vertices of G. We construct some new graphs satisfying σ > W and W > σ, respectively. In particular, infinite graphs satisfying W > σ are invented with graphs with diameter 2 and infinite ones satisfying σ > W are discovered with so-called universally diametrical graphs.