Enumeration of Independent Sets in Benzenoid Chains

Abstract

The Merrifield-Simmons index of a graph G is defined as the summation of the number i(G, k) of k-independent sets in G. It has applications in structural chemistry such as correlation with the thermodynamic properties of hydrocarbons. For this reason, enumeration of i(G, k) of molecular graphs comes into prominence. In this paper, a method based on the transfer matrix technique is presented for enumerating i(G, k) in benzenoid chains. As a consequence, for all k >= 0, each i(G, k) in arbitrary benzenoid chains is obtained via an appropriate product of three transfer matrices with dimension 5(k + 1) x 5(k + 1) and a vector. In addition, we present two algorithms to make easier application of the method so that the applicability remains the same when the k value increases.