Greedy construction of nearly regular graphs (Q1260772)

The authors study a sequence of nearly regular graphs which are built starting with the empty graph on \(n\) vertices and adding randomly one single edge at each step in such a way that at each step the new constructed edge must join some vertices with minimum degrees. The function \(f(n,m)\) is defined as the largest difference of degrees in such constructed graphs with \(n\) vertices and \(m\) edges. Main results: Theorem 1. For any positive integer \(d\) there exist positive integers \(n\), \(m\) such that \(f(n,m)\geq d\). Theorem 2. \[ \begin{alignedat}{4} &f(4k,&&\;4k^ 2+9k-3)&&\geq 3 \qquad &&\text{for }11\leq k\\ & f(4k+1,&&\;4k^ 2+10k)&&\geq 3\qquad &&\text{for }9\leq k\\ & f(4k+2,&&\;4k^ 2+11k+3) &&\geq 3\qquad &&\text{for }4\leq k\\ & f(4k+3,&&\;4k^ 2+14k+6) &&\geq 3\qquad &&\text{for }10\leq k\end{alignedat} \] Theorem 3. \[ \begin{alignedat}{3} &f(4k, &&\;4k^ 2+9k-4) &&\leq 2\\ &f(4k+1, &&\;4k^ 2+10k-1) &&\leq 2\\ & f(4k+2, &&\;4k^ 2+11k+2) &&\leq 2\\ & f(4k+3, &&\;4k^ 2+14k+5) &&\leq 2\end{alignedat} \] The paper closes with some supplementary results and problems.