Share This Article:

Do Almost All Trees Have No Perfect Dominating Set?

Full-Text HTML XML Download Download as PDF (Size:717KB) PP. 1-13
DOI: 10.4236/ojdm.2018.81001    407 Downloads   756 Views


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).

Cite this paper

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.

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.