Short cycles in random regular graphs

Abstract

Consider random regular graphs of order n and degree d = d(n) ≥ 3. Let g = g(n) ≥ 3 satisfy (d-1)2g-1 = o(n). Then the number of cycles of lengths up to g have a distribution similar to that of independent Poisson variables. In particular, we find the Show more