Enumeration and maximum number of maximal irredundant sets for chordal graphs

Abstract In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of an n -vertex chordal graph is at most 1 . 754 9 n , and these can be enumerated in time O ( 1 . 754 9 n ) . For interval graphs, we achieve the better upper bound of 1 . 695 7 n for the number of maximal irredundant sets and we show that they can be enumerated in time O ( 1 . 695 7 n ) . Finally, we show that an n -vertex forest has at most 1 . 618 1 n maximal irredundant sets that can be enumerated in time O ( 1 . 618 1 n ) . We complement the latter result by providing a family of forests having at least 1 . 529 2 n maximal irredundant sets.