The maximum degree of the rth power of a sparse random graph
Alan FriezeAditya Raut
所有作者
Alan FriezeAditya Raut
文献摘要
Let Gn,pr denote the rth power of the random graph Gn,p, where p=c/n for a positive constant c. We prove that w.h.p. the maximum degree Δ(Gn,pr)∼log(r+1)nlogn. Here log(k)n indicates the repeated application of the log-function k times. So, for example, log(3)n=logloglogn.