Trees having many minimal dominating sets

We disprove a conjecture by Skupień that every tree of order n has at most 2n/2 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.4167n. We also provide an algorithm for listing all minimal dominating sets...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2013-04, Vol.113 (8), p.276-279
Main Author: Krzywkowski, Marcin
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial bound
Combinatorial problems
Exponential algorithm
Graph theory
Listing algorithm
Minimal dominating set
Set theory
Studies
Tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We disprove a conjecture by Skupień that every tree of order n has at most 2n/2 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.4167n. We also provide an algorithm for listing all minimal dominating sets of a tree in time O(1.4656n). This implies that every tree has at most 1.4656n minimal dominating sets. ► We disprove a conjecture that every tree of order n has at most 2n/2 minimal dominating sets. ► We establish 1.4167n to be a lower bound on the running time of an algorithm for listing all m-d sets of a given tree. ► We provide an algorithm for listing all m-d sets of a tree of order n in time O(1.4656n). ► The above implies that every tree has at most 1.4656n minimal dominating sets.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2013.01.020