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

Examples of self-centered graphs (with large radius)

2010-07-17T18:13:42Z

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:

Disconnected graphs
cliques
bicliques
cycles
Take two vertices and connect them by $k\geq2$ disjoint paths of the same length
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:

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
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)

Answer by Joseph Malkevitch for Examples of self-centered graphs (with large radius)

2010-07-18T03:54:35Z

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.

Answer by Priyanka Singh for Examples of self-centered graphs (with large radius)

2012-01-02T14:17:53Z

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

Answer by Alain Valette for Examples of self-centered graphs (with large radius)

2012-01-02T15:58:51Z

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.