Chain hexagonal cacti: Matchings and independent sets (CROSBI ID 175862)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Došlić, Tomislav ; Maloy, Frode
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
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano