12
30. 3. 2015.
Counting dominating sets in cactus chains
In this paper we consider the number of dominating sets in cactus chains with triangular and square blocks. We derive and solve the recurrences satisfied by those quantities and investigate their asymptotic behavior. In triangular case we also refine the counting by computing the bivariate generating function. As a corollary, we compute the expected size of a dominating set in a triangular cactus chain of a given length.