3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – slouis Sep 14 '15 at 6:34
  • $\begingroup$ Random regular graphs are locally tree-like, so at least for $k$'s which are much smaller than the diameter, you have an answer. $\endgroup$ – Bach Sep 14 '15 at 12:46
  • $\begingroup$ 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'? $\endgroup$ – slouis Sep 15 '15 at 5:12
2
$\begingroup$

The magic words are "expander graph". A random regular graph is an expander, which means that the size of the layers is expanding until half the vertices are consumed. This (more or less) answers your questions 1, 2. As for 3, I have no idea what central/peripheral node means.

$\endgroup$
  • $\begingroup$ It is true that it is probably an expander, and it is true that it the layers are expanding - but note that (as Bach wrote in the comment on the question), the first layers are tree-like, but the large layers are totally not tree-like: there are many cycles in the big layers! In Simulations I ran the biggest layers have almost the same size and there are only 'few' edges in between the layers, which means that the 'expanding' property fades away in the most significant interesting layers! What is the size of those largest layer? Can you please detail the 'more or less'? $\endgroup$ – slouis Sep 15 '15 at 5:09
  • $\begingroup$ by 'central node' I meant - a vertex that achieves the radius of the graph. By 'peripheral node' I meant for the vertex that achieves the diameter of the graph. $\endgroup$ – slouis Sep 15 '15 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.