The maximum degree of the $r$th power of a sparse random graph

Abstract

Let $G_{n,p}^r$ denote the $r$th power of the random graph $G_{n,p}$, where $p=c/n$ for a positive constant $c$. We prove that w.h.p. the maximum degree $\Delta \left(G_{n,p}^r\right)\sim \frac{\log n}{{\log }_{(r+1)}n}$. Here ${\log }_{(k)}n$ indicates the repeated application of the log-function $k$ times. So, for example, ${\log }_{(3)}n=\log \log \log n$.