# Number of nodes in a given distance in (random) regular graph

Given a d-regular graph $G=<V,E>$ (connected, unweighted & simple), and a node $v$.

denote all nodes with distance $k$ from $v$ $$L_k=\{u\in V : dis(v,u) = k\}$$ Let's call it "the k-th layer", where the distance $dis$ is taken as the length of the minimal path.

so, for instance, $L_0 = \{v\}$ and $|L_1|=d$.

In general: What is the size of the k-th layer? specifically, what is the size of the largest layer?

Do we know the answer under any interesting assumption?

e.g.

1. Do we know the expected answer for uniformly random d-regular graph for constant $d$ and $n\rightarrow\infty$ ?

2. If we take $v \in V$ uniformly at random?

3. If we take $v$ as the central node or The peripheral node?

4. other assumptions?

• We know that in random regular graph w.h.p. there are ~$log_d(n)$ layers ([Béla Bollobás, W. Fernandez de la Vega][1]), but what is the size of each layer? – slouis Sep 14 '15 at 6:34
• Random regular graphs are locally tree-like, so at least for $k$'s which are much smaller than the diameter, you have an answer. – Bach Sep 14 '15 at 12:46
• You are correct - the first layers are tree-like, but when do they are loosing this property? this leads to further interesting question: What is the critical distance where the graph is changing from 'tree-like' to 'cyclic'? – slouis Sep 15 '15 at 5:12