Naslov
Chain hexagonal cacti: Matchings and independent sets

Autori
Došlić, Tomislav ; Maloy, Frode

Izvornik
Discrete mathematics (0012-365X) 310 (2010); 1176-1190

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Cactus graph; Matching polynomial; Independence polynomial; Hexagonal cactus

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA