\tbGraphs with prescribed radius, diameter, and center

If $rad(G)=diam(G)$, then $G$ is its own center. Therefore, $H=C(G)$ and $rad(G)=diam(G)$ if and only $H\simeq G$ and $rad(H)=diam(H)$.

If $rad(G)=1$, then each central vertex of $G$ is adjacent to every other vertex of $G$. Therefore, if $H\cong C(G)$ then $H$ must be a complete graph, and each vertex of $H$ must be adjacent to each vertex of $V(G)\setminus V(H)$. Furthermore, since all central vertices of $G$ are in $V(H)$, it must be that every $v\in V(G)\setminus V(H)$ has a non-neighbor in $G$ in $V(G)\setminus V(H)$.

Let “$\vee$” stand for the join of two graphs: $X\vee Y$ is formed by taking disjoint copies of $X$ and $Y$ and then adding in every edge $xy$, $x\in V(X),y\in V(Y)$. By the paragraph above, when $r=1$, $d=2$, the only $H$ for which a solution $G$ can exist are $H=K_{t},t>0$, and the only possible solutions are $K_{t}\vee Y$ in which $Y$ is a graph with $|V(Y)|>1$ and for each $y\in V(Y)$, the degree deg$(y)$ of $y\in V(Y)$ satisfies deg${}_{Y}(y)<|V(Y)|-1$.

Every such $G=K_{t}\vee Y$ satisfies $rad(G)=1$, $diam(G)=2$, and $C(G)=K_{t}$, so we have completely characterized the values of $H(H=K_{t})$ for which our problem with $r=1,d=2$ has a solution, and all possible solutions ($G=K_{t}\vee Y$, as above).

The proof is straightforward. Note that the assumption that $rad(X)=\varepsilon_{X}(h)\geq 2$ plays a role in the proof that $H\cong C(G)$.

For instance, the graph in Figure 1 is obtained from $X=P_{5}$, the path on 5 vertices, by the device of Proposition 1. The generalization to the solution of our problem for all $H$ when $d=2r\geq 4$ uses the device of Prop. 1 with $X=P_{2r+1}$.

In Figure 2 we have a graph $X$ with a single central vertex $h$ such that $rad(X)=r$, $diam(G)=2r-1$, for arbitrary $r\geq 2$. By Proposition 1, this shows that every graph $H$ can be the center of a graph $G$ of radius $r$ and diameter $2r-1$, for every $r\geq 2$.

For those who enjoy variety, we can vary $X$ to the graph $Y$ shown in Figure 3, which gives another solution to our problem when $d=2r$ and $H$ arbitrary.

If you have been paying attention, you might exclaim: why do we need this? Hedetniemi’s construction already gives us solutions of our problem in the case $d=2r\geq 4$. Yes, bur Figure 3 gives a different solution, and different solutions of our problem contribute to the solution of a problem that towers over ours: given positive integers $r$ and $d$ satisfying $1<r<d\leq 2r$, and a graph $H$, find all possible graphs $G$ satisfying $rad(G)=r$, $diam(G)=d$, and $C(G)\cong H$. In view of Proposition 1, in pursuit of this larger problem, it is appropriate to pose the following: given $d$ and $r$ as above, find all graphs $X$ such that $rad(X)=r$, $diam(X)=d$, and $C(X)=K_{1}$.

Moreover, the alternative solutions to the $d=2r$ case provide a related problem: what properties characterize those graphs with $d=2r$ and center $K_{1}$? The majority of graphs constructed with center $K_{1}$ in fact had $d=2r$, and the solution to this problem will considerably narrow down the larger problem.

In Figure 4, we have, for $r\geq 2$, a graph of radius $r$ and diameter $r+1$, and a graph of radius $r$ and diameter $r+\lceil\frac{r}{3}\rceil$, both with a single central vertex.

The strategy referred to, applicable only when $H$ is connected is: attach pairwise vertex-disjoint paths to the vertices of $H$. This trick appears to be of use only in a special class of cases.

The proof is straightforward.