Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)
share|improve this question
3  
Any vertex transitive graph. –  Emil Jul 17 '10 at 19:41
    
See also mathoverflow.net/questions/64746/… –  Alain Valette Jan 2 '12 at 15:27
add comment

3 Answers 3

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
3  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.