Maximal Independent Sets in Polygonal Cacti

Abstract

Counting the number of maximal independent sets of graphs was started over $50$ years ago by Erdős and Mooser. The problem has been continuously studied with a number of variations. Interestingly, when the maximal condition of an independent set is removed, such the concept presents one of topological indices in molecular graphs, the so called Merrifield-Simmons index. In this paper, we applied the concept of bivariate generating function to establish the recurrence relations of the numbers of maximal independent sets of regualr $n$-gonal cacti when $3\le n\le 6$. By the ideas on meromorphic functions and the growth of power series coefficients, the asymptotic behaviors through simple functions of these recurrence relations have been established.