graph theoryreference-request
In basic graph theory books, we learn that the radius (rad) and diameter (diam) satisfy
$$rad(G) \leq diam(G) \leq 2 rad(G)$$
I have seen books talk about graphs for which $rad(G) = diam(G)$. These graphs are called self-centered graphs. But, I have never seen anything on graphs satisfying the other bound, $diam(G) = 2 rad(G)$. I have googled for papers on the topic many times and never come up with anything. Do any of you know of any such papers/books that might mention this?
Thanks
Circulant graphs can be used to realize the $\lfloor n\Delta/2 \rfloor$ bound in a large number of cases, and in the other cases, we can modify them slightly to achieve this bound.
For example, when $n=10$ and $\Delta=6$, we can take the distances $\{1,2,3\}$, which gives:
For example, when $n=10$ and $\Delta=5$, we can take the distances $\{1,2,5\}$, which gives:
For example, when $n=11$ and $\Delta=6$, we can take the distances $\{2,3,4\}$, which gives:
Finally, when $n$ is odd and $\Delta$ is odd (so $\Delta \leq n-2$), $n\Delta/2$ is not an integer, so we can't achieve the maximum with circulant graphs. The best we could possibly do is $\lfloor n\Delta/2 \rfloor$. To achieve this:
We take a $(\Delta-1)$-regular graph as above, but do not take distance $1$ edges (we need to take at most $(\Delta-1)/2 \leq (n-3)/2$ distances, so this is possible).
We observe that the edges of distance $1$ form a Hamilton cycle in the complement of the graph. We pick $(n-1)/2$ disjoint edges from this Hamilton cycle (i.e., no two edges share an endpoint), and add them to our construction.
For example, when $n=11$ and $\Delta=7$, we can take the above $6$-regular graph and add in edges around the outside as follows:
This gives $\lfloor n\Delta/2 \rfloor$ edges in every case (as expected).
There are such graphs.
I'll give you a hint.
Hint 1. Which graph is the first one you should think of when trying to find a counterexample or disprove something?
Hint 2. 10 vertices, 3-regular.
Best Answer
I was asked to post the comment as an answer, so here it is:
Maybe that property is uninteresting? For any graph of size $n$ with single connected component, pick any vertex, and then create 2 paths of length $n$ from this vertex by adding $2n$ new vertices (and $2n$ edges). Not much has changed, but now $\mathrm{diam}(G)=2\mathrm{rad}(G)$ now.