# Examples of self-centered graphs (with large radius)

A self-centered graph is a graph whose diameter equals its radius. I am looking for examples of families of self-centered graphs. Here are some examples I know:

1. Disconnected graphs
2. cliques
3. bicliques
4. cycles
5. Take two vertices and connect them by $k\geq2$ disjoint paths of the same length
6. take a self-centered graph and replace every edge $uv$ by a 4-cycle $uxvy$ (e.g. when you start with a single edge and repeat this procedure k times you have the so-called k-th diamond graph which btw. is a nice example of a graph metric which needs high distortion to embed into Euclidean space)

Do you know some further nice examples? Especially I am looking for examples with large radius (for my purposes that means radius of size $\omega(\log n)$ where $n$ is the number of vertices) which are nonplanar. Also other ways than 6. to systematically construct self-centered graphs would be interesting.

edit: More examples:

1. There is a complete list of all self-centered graphs with diameter 2 that have minimum number of edges in: http://www3.interscience.wiley.com/journal/119436272/abstract
2. For every finite group $\Gamma$ there is a self-centered graph whose automorphism group is isomorphic to $\Gamma$ (S.-M. Lee, P.-C. Wang, On groups of automorphisms of self-centered graphs,. Bull. Math. Soc. Sci. Math. Roumanie)
-
Any vertex transitive graph. – Emil Jul 17 '10 at 19:41
– Alain Valette Jan 2 '12 at 15:27

There is a discussion of self-centered graphs in:

Fred Buckley and Frank Harary, Distances in Graphs, Addison-Wesley, 1990.

The discussion of self-centered graphs is on pages 38-42 (and a few other pages), and Fred Buckley wrote some other papers on this subject but I don't have the references immediately available.

-
Thank you for the reference. A quick google search yields this survey paper by Buckley: www3.interscience.wiley.com/journal/119436272/abstract – Paolo Ketter-Umbanza Jul 18 '10 at 10:24

As Emil mentioned, any vertex-transitive graph has a radius equal to its diameter. On the other hand, families of $k$-regular graphs have a diameter in $\Omega(\log n)$, where $n$ is the number of vertices. Combining both observations you get many examples with radius in $\Omega(\log n)$. You can cross with $K_5$ to make them non-planar.

-

complete graphs are also self centered graphs. infact 1-self centered graphs

-
Doesn't that fall under the heading, "cliques", which was number 2 on the list of OP? – Gerry Myerson Jan 2 '12 at 14:52