Name
Abstract | ||
|---|---|---|
We disprove a conjecture by Skupien that every tree of order n has at most 2^n^/^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.4167^n. We also provide an algorithm for listing all minimal dominating sets of a tree in time O(1.4656^n). This implies that every tree has at most 1.4656^n minimal dominating sets. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ipl.2013.01.020 | Inf. Process. Lett. |
Keywords | Field | DocType |
order n,minimal dominating set,time o,n minimal dominating set,tree | Discrete mathematics,Combinatorics,Dominating set,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
113 | 8 | 0020-0190 |
Citations | PageRank | References |
9 | 0.64 | 8 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcin Krzywkowski | 1 | 16 | 6.22 |