Trees having many minimal dominating sets

Trees having many minimal dominating sets

0.00 Avg rating0 Votes
Article ID: iaor20132359
Volume: 113
Issue: 8
Start Page Number: 276
End Page Number: 279
Publication Date: Apr 2013
Journal: Information Processing Letters
Authors:
Keywords: sets
Abstract:

We disprove a conjecture by Skupien that every tree of order n has at most 2 n / 2 equ1 minimal dominating sets. We construct a family of trees of both parities of the order for which the number of minimal dominating sets exceeds 1.4167 n equ2. We also provide an algorithm for listing all minimal dominating sets of a tree in time O ( 1.4656 n ) equ3. This implies that every tree has at most 1.4656 n equ4 minimal dominating sets.

Reviews

Required fields are marked *. Your email address will not be published.