Recurrence among trees with most numerous efficient dominating sets
Dorota Bród, Zdzisław Skupień
Abstract
A dominating set D of vertices in a graph G is called an
efficient dominating set if the distance between any two vertices
in D is at least three. A tree T of order n is called
maximum if T has the largest number of efficient dominating sets
among all n-vertex trees. A constructive characterization of all
maximum trees is given. Their structure has recurring aspects with
period 7. Moreover, the number of efficient dominating sets in
maximum n-vertex trees is determined and appears to be
exponential. Also the number of maximum n-vertex trees is shown
to be bounded below by an increasing exponential function in n.
Full Text: PDF PostScript