Counting dominating sets in generalized series-parallel graphs
Min-Sheng Lin · Discrete Mathematics Algorithms and Applications · 2019
Counting dominating sets in a graph is a #P-complete problem even in planar graphs. This paper studies this problem for generalized series-parallel graphs, which are a subclass of planar graphs. This work develops some linear-time algorithms for counting dominating sets and their two variants, independent dominating sets and connected dominating sets in generalized series-parallel graphs.