On a conjecture of Knuth about forward and back arcs
arXiv:2301.05704
Abstract
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.
6 pages, 0 figures