| Popis: |
An oriented graph G→ is said to have an efficient dominating set S if S is a set of vertices of G→ and for each vertex v of G→, either v is in S and v is adjacent to no other vertex in S, or v 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. |
Full Text from ScienceDirect