<p>Let $G=(V,E)$ be an undirected, random $r$-regular graph.</p>

<p>Let $s,t\in V$, and denote by $N(v)=\{u\in V\mid (u,v)\in E\}$ the neighborhood of $v$.</p>

<p>I'm looking for the distribution of the number of neighbors of $t$ which are closest to $s$, that is, let
$$C = \text{argmin}_{u\in N(t)}d(s,u)$$</p>

<p>($d:V\times V\to \mathbb N$ is the unweighted distance function which counts the number of hops between the vertices, i.e., the length of the shortest path).</p>

<ul>
<li><strong>What is the distribution of $|C|$? (fixing $r$ and $n=|V|$)</strong></li>
</ul>

<hr>

<p>I'm also interested in a few simpler questions:</p>

<ul>
<li>What is $\mathbb E (|C|)$?</li>
<li>What is $\Pr(|C| &gt; 1)$?</li>
<li>Can we find any of these quantities for $r=4$, which is especially interesting for me?</li>
</ul>

<hr>

<p>The motivation for the question comes from peer-to-peer routing networks (of a specific type, which can approximately be represented as regular graphs).
Assume that the source node $s$ broadcasts a message to all vertices such that every vertex propagates the message upon arrival. I'm interested in the number of nodes we need to query before we find a neighbor that received the message already.</p>

CC BY-SA 3.0
2015-06-16T13:03:50.500Z
It sounds as if you're assuming that the result is independent of $|V|$ - is that the case?
Klaus Draeger
CC BY-SA 3.0
2015-06-16T13:10:43.467Z
@KlausDraeger - I don't think the result is independent of $|V|$ (e.g., if $|V|=5$, then the only $4$-regular graph is $K_5$, in which all of the neighbors are $1$ hop away from $s$, but this is not the usual case for large $|V|$).
R B
CC BY-SA 3.0
2015-06-16T13:16:16.160Z
That's why I asked, yes. What about the possibility that $G$ is disconnected? Is $C$ the whole connected component of $s$ except $s$ itself?
Klaus Draeger
CC BY-SA 3.0
2015-06-16T13:19:47.257Z
@KlausDraeger - $G$ may be disconnected, in which case the distance is $\infty$. $C$ is the set of neighbors of $t$, which may or may not include $s$ (but it does not contain $t$). This means that $1\le|C|\le r$.
R B
<graph-theory><randomness><random-graphs>
How many neighbors does a vertex has which are closest to a source vertex in random regular graphs?
R B
# How many neighbors does a vertex has which are closest to a source vertex in random regular graphs?

(Asked by: username_0 on 2015-06-15)

Let $G=(V,E)$ be an undirected, random $r$-regular graph.

Let $s,t\in V$, and denote by $N(v)=\{u\in V\mid (u,v)\in E\}$ the neighborhood of $v$.

I'm looking for the distribution of the number of neighbors of $t$ which are closest to $s$, that is, let
$$C = \text{argmin}\_{u\in N(t)}d(s,u)$$

($d:V\times V\to \mathbb N$ is the unweighted distance function which counts the number of hops between the vertices, i.e., the length of the shortest path).

* **What is the distribution of $|C|$? (fixing $r$ and $n=|V|$)**

---

I'm also interested in a few simpler questions:

* What is $\mathbb E (|C|)$?
* What is $\Pr(|C| > 1)$?
* Can we find any of these quantities for $r=4$, which is especially interesting for me?

---

The motivation for the question comes from peer-to-peer routing networks (of a specific type, which can approximately be represented as regular graphs).
Assume that the source node $s$ broadcasts a message to all vertices such that every vertex propagates the message upon arrival. I'm interested in the number of nodes we need to query before we find a neighbor that received the message already.

**Tags:** graph-theory, randomness, random-graphs
> **Comments:**
> **username_1**: It sounds as if you're assuming that the result is independent of $|V|$ - is that the case?  
> **username_0**: @KlausDraeger - I don't think the result is independent of $|V|$ (e.g., if $|V|=5$, then the only $4$-regular graph is $K_5$, in which all of the neighbors are $1$ hop away from $s$, but this is not the usual case for large $|V|$).  
> **username_1**: That's why I asked, yes. What about the possibility that $G$ is disconnected? Is $C$ the whole connected component of $s$ except $s$ itself?  
> **username_0**: @KlausDraeger - $G$ may be disconnected, in which case the distance is $\infty$. $C$ is the set of neighbors of $t$, which may or may not include $s$ (but it does not contain $t$). This means that $1\le|C|\le r$.  

---

## 0 answers

