Enumeration of Independent Sets in Benzenoid Chains
MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY, vol.88, no.1, pp.93-107, 2022 (SCI-Expanded, Scopus)
- Publication Type: Article / Article
- Volume: 88 Issue: 1
- Publication Date: 2022
- Doi Number: 10.46793/match.88-1.093o
- Journal Name: MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY
- Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, zbMATH
- Page Numbers: pp.93-107
- Open Archive Collection: AVESIS Open Access Collection
- Bursa Uludag University Affiliated: Yes
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.