Efficient dominating sets in labeled rooted oriented trees Original Research Article

An oriented graph image is said to have an efficient dominating set S if S is a set of vertices of image and for each vertex image of image, either image is in S and image is adjacent to no other vertex in S, or image is not in S but is adjacent from precisely one vertex of S. Not every oriented graph has an efficient dominating set and some oriented graphs may have more than one efficient dominating set. Barkauskas and Host [Finding efficient dominating sets in oriented graphs, Congr. Numer. 98 (1993) 27–32] showed that the problem of determining whether or not an oriented graph has an efficient dominating set is NP-complete. For a tree T, each orientation of T can give rise to at most one efficient dominating set. Yue [The number of efficient dominating sets in oriented trees, to appear] determined the number of efficient dominating sets among all unlabeled oriented trees of order p for each p up to 150, and the asymptotic behavior for the number of efficient dominating sets in unlabeled oriented trees. In this paper, combinatorial enumeration techniques are used to derive the exact formulas for the number of efficient dominating sets among all labeled rooted oriented trees. These formulas are used to find the number of efficient dominating sets among all labeled rooted oriented trees of order p for each p up to 45. Finally, the asymptotic formulas for the number of efficient dominating sets among all labeled rooted oriented trees are also determined.