Para amplios rangos del parámetro $p$$G(n,p)$, el número de vértices con un mínimo de excentricidad ha trivial de distribución.
En primer lugar, considerar los centros en $G(n,p)$ donde $p \in (0,1)$ es fijo. Con alta probabilidad, el diámetro es de $2$ (ver Bollob$\'{a}$s "Grafos Aleatorios"). El mínimo mayor distancia al resto de vértices es $1$ o $2$. Para un vértice a distancia uno de otros vértices, necesariamente está en un borde con cada uno de los otros vértices. Así
\begin{align*}
P(\text{there is a vertex with eccentricity} 1) &\leq n P(v_1 \text{ is adjacent to every other vertex}) \\&= n p^{n-1} \to 0,
\end{align*}
desde $p<1$ fijo. Por lo tanto, w.h.p. cada vértice de $G(n,p)$ está en el centro.
Ahora un poco más general: Deje $d=d(n)\geq 3, p=p(n)$ ser tal que
$$d \leq 0.33 \frac{\ln n}{\ln \ln n},$$
$$ \frac{n^{1/(d+1)}\ln n}{n} \leq p \leq \frac{1}{2} \frac{n^{1/d}}{n}. $$
Entonces w.h.p. $G(n,p)$ tiene el diámetro $d+1$, de volver a ver Bollobas "Grafos Aleatorios". Ahora quiero demostrar que cada vértice en $G(n,p)$ ha excentricidad $d+1$. Tenga en cuenta que
\begin{align*}
P\Big(deg(v_1) \geq \left(1.1\right)np\Big) &= P\Big( Bi(n-1,p) \geq \left(1+.1\right)np \Big) \\&\leq \exp \left( - \frac{.01}{3} np \right) \leq \exp \left( - n^{1/(d+1)}/\ln^2n\right),
\end{align*}
donde usted puede encontrar el binomio cola enlazada en Janson, Luczak, Rucinski "Grafos Aleatorios".
Por una unión obligado a todos los vértices, nos encontramos con que $w.h.p.$ grado máximo, $\Delta$, es en la mayoría de las $(1.1)np \leq 0.55 n^{1/d}$. Tenga en cuenta que el número de vértices alcanzables dentro de la distancia $i$ es en la mayoría de las $1+ \Delta+\Delta^2+\ldots+ \Delta^i$. Así, en el caso de que $\Delta \leq 0.55 n^{1/d}$, el número de vértices alcanzables desde cualquier específicos vértice $v,$ dentro de la distancia $d$ es en la mayoría de los
\begin{align*}
1+(0.55 n^{1/d}+\ldots \left(0.55 n^{1/d}\right)^d &= (1+o(1))\left(0.55 n^{1/d}\right)^d \\& \leq 0.5 n.
\end{align*}
En otras palabras, w.h.p. cada vértice de $G(n,p)$ ha excentricidad, al menos,$d+1$.
Tenga en cuenta que me han mantenido lejos del umbral al $G(n,p)$ cambios de diámetro de $d+1$ para el diámetro de $d$,$p=\frac{n^{1/d}}{n} \left( 2 \ln n + O_p(1)\right)^{1/d}$. Me imagino que a medida que el enfoque de este umbral, usted podría obtener no trivial de comportamiento para el número de centros (Por ejemplo, en la crítica de la ventana, $p=\frac{n^{1/d}}{n}\left(2 \ln n + c\right), c \in \mathbb{R}$, espero que el mínimo de la excentricidad a ser $d$ y el número de vértices que se $\textbf{not}$ centros es asintóticamente Poisson).
