A structural theorem about the distribution of simplicial vertices in a chordal graph.An algorithm for enumerating minimal dominating sets in a chordal graph.Upper bound on number of minimal dominating sets improved from 1.6181 n to 1.5214 n . The maximum number of minimal dominating sets in a chordal graph on n vertices is known to be at most 1.6181 n . However, no example of a chordal graph with more than 1.4422 n minimal dominating sets is known. In this paper, we narrow this gap between the known upper and lower bounds by showing that the maximum number of minimal dominating sets in a chordal graph is at most 1.5214 n .
['Faisal N. Abu-Khzam', 'Pinar Heggernes']
Enumerating minimal dominating sets in chordal graphs