On the Number of Minimum Dominating Sets in Trees
The class of trees in which the degree of each vertex does not exceed an integer 𝑑 is considered. It is shown that, for 𝑑=4, each 𝑛-vertex tree in this class contains at most (√2)^𝑛 minimum dominating sets (MDS), and the structure of trees containing precisely (√2)^𝑛 MDS is described. On the other hand, for 𝑑=5, an 𝑛-vertex tree containing more than (1/3)⋅1.415^𝑛 MDS is constructed for each 𝑛≥1. It is shown that each 𝑛-vertex tree contains fewer than 1.4205^𝑛 MDS.