On a conjecture of Knuth about forward and back arcs

01/13/2023

∙

by   Zipei Nie, et al.

∙

0

∙

share

Following Janson's method, we prove a conjecture of Knuth: the numbers of forward and back arcs for the depth-first search (DFS) in a digraph with a geometric outdegree distribution have the same distribution.