7
$\begingroup$

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)
$\endgroup$
2

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
1
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

As commented in this linked post, the Rubik's cube state graph is self centered.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • 4
    $\begingroup$ Doesn't that fall under the heading, "cliques", which was number 2 on the list of OP? $\endgroup$ Jan 2, 2012 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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