Do Almost All Trees Have No Perfect Dominating Set? ()
ABSTRACT
A graph G is said to have a perfect 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 to precisely one vertex of S. A graph G may have
none, one or more than one perfect dominating sets. The problem of determining
if a graph has a perfect dominating set is NP-complete. The problem of
calculating the probability of an arbitrary graph having a perfect dominating
set seems also difficult. In 1994 Yue [1] conjectured that
almost all graphs do not have a perfect dominating set. In this paper, by
introducing multiple interrelated generating functions and using combinatorial
computation techniques we calculated the number of perfect dominating sets
among all trees (rooted and unrooted) of order n for each n up to 500.
Then we calculated the average number of perfect dominating sets per tree
(rooted and unrooted) of order n for
each n up to 500. Our computational
results show that this average number is approaching zero as n goes to infinity thus suggesting that Yue’s conjecture is true
for trees (rooted and unrooted).
Share and Cite:
Yue, B. (2018) Do Almost All Trees Have No Perfect Dominating Set?.
Open Journal of Discrete Mathematics,
8, 1-13. doi:
10.4236/ojdm.2018.81001.
Cited by
No relevant information.