An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne–Goodman–Hedetniemi algorithm

A random recursive tree on nn vertices is either a single isolated vertex (for n=1n=1) or is a vertex vnvn connected to a vertex chosen uniformly at random from a random recursive tree on n−1n−1 vertices. Such trees have been studied before [R. Smythe, H. Mahmoud, A survey of recursive trees, Theory of Probability and Mathematical Statistics 51 (1996) 1–29] as models of boolean circuits. More recently, Barabási and Albert [A. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509–512] have used modifications of such models to model for the web and other “power-law” networks.A minimum (cardinality) dominating set in a tree can be found in linear time using the algorithm of Cockayne et al. [E. Cockayne, S. Goodman, S. Hedetniemi, A linear algorithm for the domination number of a tree, Information Processing Letters 4 (1975) 41–44]. We prove that there exists a constant d≃0.3745…d≃0.3745… such that the size of a minimum dominating set in a random recursive tree on nn vertices is dn+o(n)dn+o(n) with probability approaching one as nn tends to infinity. The result is obtained by analysing the algorithm of Cockayne, Goodman and Hedetniemi.