MSI Weekly Bulletin - Week starting Monday 5 February, 2007

A random recursive tree on $n$ vertices is either a single isolated vertex (for $n=1$) or a vertex $v_n$ connected to a vertex chosen uniformly at random in a random recursive tree on $n-1$ vertices. Such trees have been studied before as models of boolean circuits. More recently, modifications of such models have been used to model the web and other "power-law" networks. We prove that there exists a constant $\gamma \simeq 0.3745 ...$such that the size of a smallest dominating set in a random recursive tree on $n$ vertices is $\gamma n+o(n)$ with probability approaching one as $n$ tends to infinity. The result is obtained by analysing an algorithm proposed by Cockayne {it et al.} (1975). Our technique also leads to tight bounds on the independence number of random recursive trees. BIO: http://www.csc.liv.ac.uk/~michele/

Generalized second order differential operators of the form d/dm d/dn are considered, where m and n are finite atomless Borel measures with compact supports on the real line. If the Hausdorff dimension of supp m is less than one, such an operator allows an interpretation as a measure geometric Laplacian for this fractal, which has similar analytical properties to the Euclidean Laplacian. In the special case of self-similar measures - Hausdorff measures or, more general, self-similar measures with arbitrary weights - , spectral asymptotics are presented. We apply these results to the special case where n is the Lebesgue measure.