Optimal sets of vertices in random recursive trees

Michele Zito (Department of Computer Science, The University of Liverpool, UK)

MSI Computational Mathematics (formerly AdvCom) Seminar Series

DATE: 2007-02-05
TIME: 11:00:00 - 12:00:00
LOCATION: John Dedman Seminar Room G35
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
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/