The Number of Orientations of a Tree Admitting an Efficient Dominating Set

Abstract

We give recursive methods for enumerating the number of orientations of a tree which can be efficiently dominated. We also examine the maximum number, ${\eta }_q$, of orientations admitting an efficient dominating set in a tree with $q$ edges. While we are unable to give either explicit formulas or recursive methods for finding ${\eta }_q$, we are able to show that the growth rate of the sequence $⟨{\eta }_q⟩$ stabilizes by showing that $\underset{q\to \mathrm{\infty }}{lim}{\eta }_q^{\frac{1}{q}}$ exists.