engleski

Chain hexagonal cacti: Matchings and independent sets

In this paper we consider three classes of chain hexagonal cacti and study theirmatching and independence related properties. Explicit recurrences are derived for their matching and independence polynomials, and explicit formulae are presented for the number of matchings and independents sets of certain types. Bivariate generating functions for the number of matchings and independent sets of certain types are also computed and then used to deduce the expected size of matchings and independent sets in chains of given length. It is shown that the extremal chain hexagonal cacti with respect to the number of matchings and of independent sets belong to one of the considered types. Possible directions of further research are discussed.

Cactus graph; Matching polynomial; Independence polynomial; Hexagonal cactus

nije evidentirano