I find a very interesting concept "center" while learning basic graph theory. A center of graph $G$ is a vertex with the minimal greatest distance (eccentricity) to other nodes in $G$. Now I’m curious about the number of centers in a graph.
I’ve learned that a tree has one or two adjacent centers, and I also find that every vertex is a center for a complete graph. But how about other kinds of graphs? I noticed that computer programs can help calculate the exact number of centers for finite graphs. But they cannot handle the cases with infinite graphs.
Is there any analytical result on the number of centers of a infinite connected graph, for example, the random regular graph and the giant component of random graph $G(n,p)$ for $n \to \infty$?
I'm open to whatever can be suggested. Thanks!
For large ranges of the parameter $p$ in $G(n,p)$, the number of vertices with minimum eccentricity has trivial distribution.
First, consider centers in $G(n,p)$ where $p \in (0,1)$ is fixed. With high probability, the diameter is $2$ (see Bollob$\'{a}$s "Random Graphs"). Either the minimum greatest distance to other vertices is $1$ or $2$. For a vertex to be distance one from other vertices, necessarily it is in an edge with each other vertex. So
\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*} since $p<1$ fixed. Therefore w.h.p. each vertex of $G(n,p)$ is in the center.
Now a little more general: Let $d=d(n)\geq 3, p=p(n)$ be such that $$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}. $$ Then w.h.p. $G(n,p)$ has diameter $d+1$, again see Bollobas "Random Graphs". Now I wish to show that each vertex in $G(n,p)$ has eccentricity $d+1$. Note that \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*} where you can find the binomial tail bound in Janson, Luczak, Rucinski "Random Graphs".
By an union bound over all vertices, we find that $w.h.p.$ maximum degree, $\Delta$, is at most $(1.1)np \leq 0.55 n^{1/d}$. Note that the number of vertices reachable within distance $i$ is at most $1+ \Delta+\Delta^2+\ldots+ \Delta^i$. Thus on the event that $\Delta \leq 0.55 n^{1/d}$, the number of vertices reachable, from any specific vertex $v,$ within distance $d$ is at most \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*} In other words, w.h.p. each vertex of $G(n,p)$ has eccentricity at least $d+1$.
Note that I have stayed away from the threshold when $G(n,p)$ changes from diameter $d+1$ to diameter $d$, which is $p=\frac{n^{1/d}}{n} \left( 2 \ln n + O_p(1)\right)^{1/d}$. I imagine as you approach this threshold, you would obtain non-trivial behavior for the number of centers (For instance, in the critical window, $p=\frac{n^{1/d}}{n}\left(2 \ln n + c\right), c \in \mathbb{R}$, I expect the minimum eccentricity to be $d$ and the number of vertices which are $\textbf{not}$ centers is asymptotically Poisson).