Maximal paths in random dynamic graphs (Q1104336)

The class of dynamic graphs \(g(m,k,N)\) is composed for digraphs with the following structure: the \(m(k+1)\) nodes are arranged in \(k+1\) stages each containing m nodes, and each of the N arcs points from stage i to stage \(i+1\) for \(i=1,2,...,k\). There are exactly \(M=\begin{pmatrix} m^ 2k\\ N \end{pmatrix}\) labeled digraphs in the class g(m,k,N). If each of these M dynamic graphs is assigned the probability \(1/M\), the random dynamic graph \(G_ N\) is obtained. The paper shows that if \(N/km\leq B\leq 1\) then \(G_ N\) contains no directed k-path from stage 1 to stage \(k+1\) with probability approaching unity as m and k approach infinity; that if \(N/km\to \infty\) and k/m\(\leq c<\infty\), then there are many k-paths in \(G_ N\) with probability approaching unity; that the same results hold for the random dynamic graph \(G_ p\) where each potential arc exists with probability \(p=N/m^ 2k\); and that if \(N=m^ 2k\) \((p=1)\) and arc i has random weight \(C_ i\) \((i=1,2,...,N)\) a good upper bound on the value of the minimum weight k-path and an exact value for the bottleneck problem on k-paths as \(m,k\to \infty\) but \(k/m\leq C<\infty\) obtained.