Abstract

We study the Depth-First Search algorithm, applied to a random digraph ($=$ directed graph). The random digraph is constructed by giving the vertices i.i.d.\ outdegrees, and choosing the endpoint of all arcs independently and uniformly at random. (Loops and multiple edges are allowed, but not important.) The Depth-First Search can be regarded as building a forest which eventually contains all vertices. One important property is the depth of vertices in this forest, i.e.\ the distance to the root. A particularly simple case is when the outdegree distribution is geometric. Its lack of memory implies that that the depths of the evrtices form a Markov process, which can be analyzed. For a general outdegree distribution, this is no longer true; as a substitute, we study a related process, which is Markov, and then are able to draw conclusions also for the depth. (Based on joint work with Philippe Jacquet.)