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]
References
[1]
Yue, B. (1994) Almost all Graphs Do Not Have a Perfect Domination Set, Personal Notes.
[2]
Livingston, M.L. and Stout, Q.F. (1988) Distributing Resources in Hypercube Computers. Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Application, Pasadena, 19-20 January 1988, 222-231. https://doi.org/10.1145/62297.62324
[3]
Hamming, R.W. (1950) Error Detecting and Error Correcting Codes. The Bell System Technical Journal, 29, 147-160. https://doi.org/10.1002/j.1538-7305.1950.tb00463.x
[4]
Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York.
[5]
Johnson, D.S. (1985) The NP-Completeness Column: An Ongoing Guide. Journal of Algorithms, 6, 434-451. https://doi.org/10.1016/0196-6774(85)90012-4
[6]
Livningston, M. and Stout, Q.F. (1990) Perfect Dominating Sets. Congressus Numerantium, 79, 187-203.
[7]
Harary, F. and Palmer, E.M. (1973) Graphical Computation. Academic Press, New York.
[8]
Chartrand, G. and Lesniak, L. (1986) Graphs and Digraphs. 2nd Edition, Wadsworth and Brooks/Cole, Monterey, CA.
[9]
Rudin, W. (1976) Principles of Mathematical Analysis. McGraw-Hill, Boston.
[10]
Otter, R. (1948) The Number of Trees. Annals of Mathematics, 49, 583-599. https://doi.org/10.2307/1969046
[11]
Pólya, G. and Szego, G. (2011) Problems and Theorems in Analysis I, Classics in Mathematics. Springer.
