Examples of self-centered graphs (with large radius) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T12:08:23Z http://mathoverflow.net/feeds/question/32301 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32301/examples-of-self-centered-graphs-with-large-radius Examples of self-centered graphs (with large radius) Paolo Ketter-Umbanza 2010-07-17T18:13:42Z 2012-01-02T15:58:51Z <p>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:</p> <ol> <li>Disconnected graphs</li> <li>cliques</li> <li>bicliques</li> <li>cycles</li> <li>Take two vertices and connect them by $k\geq2$ disjoint paths of the same length</li> <li>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)</li> </ol> <p>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.</p> <p><strong>edit:</strong> More examples: </p> <ol> <li>There is a complete list of all self-centered graphs with diameter 2 that have minimum number of edges in: <a href="http://www3.interscience.wiley.com/journal/119436272/abstract" rel="nofollow">http://www3.interscience.wiley.com/journal/119436272/abstract</a></li> <li>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)</li> </ol> http://mathoverflow.net/questions/32301/examples-of-self-centered-graphs-with-large-radius/32339#32339 Answer by Joseph Malkevitch for Examples of self-centered graphs (with large radius) Joseph Malkevitch 2010-07-18T03:54:35Z 2010-07-18T03:54:35Z <p>There is a discussion of self-centered graphs in:</p> <p>Fred Buckley and Frank Harary, Distances in Graphs, Addison-Wesley, 1990.</p> <p>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.</p> http://mathoverflow.net/questions/32301/examples-of-self-centered-graphs-with-large-radius/84747#84747 Answer by Priyanka Singh for Examples of self-centered graphs (with large radius) Priyanka Singh 2012-01-02T14:17:53Z 2012-01-02T14:17:53Z <p>complete graphs are also self centered graphs. infact 1-self centered graphs</p> http://mathoverflow.net/questions/32301/examples-of-self-centered-graphs-with-large-radius/84750#84750 Answer by Alain Valette for Examples of self-centered graphs (with large radius) Alain Valette 2012-01-02T15:58:51Z 2012-01-02T15:58:51Z <p>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.</p>