A Limit Theorem for the Six-length of Random Functional Graphs with a Fixed Degree Sequence

  • Kevin Leckey
  • Nick Wormald


We obtain results on the limiting distribution of the six-length of a random functional graph, also called a   functional digraph or random mapping, with given in-degree sequence. The six-length  of a vertex $v\in V$  is defined from the associated mapping, $f:V\to V$, to be the maximum $i\in V$ such that the elements $v, f(v), \ldots, f^{i-1}(v)$ are all distinct. This has relevance to the study of algorithms for integer factorisation.

Article Number