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

Let $X=(V,E)$ be a finite, connected, regular graph with diameter $D$. Is it true that, for every $x\in V$, there exists $y\in V$ such that $d(x,y)=D$? (the answer is clearly yes if $X$ is vertex-transitive).

share|improve this question
1  
What about this one: vertices P, A, B, C, X, Y, Z, U, V, W, edges PU, PV, PW, UA, UX, VB, VY, WC, WZ, BC, CA, AB, VW, WU, UV ? Everything reachable in 2 edges from P, but diameter apparently 3. –  darij grinberg May 11 '11 at 21:30
    
A bipartite counterexample might be more interesting. –  darij grinberg May 11 '11 at 21:35
2  
Here's a bipartite example: vertices A B 0 1 2 3 4 5 6 7 8 9, edges 0A, 0B, 01, 12, 13, 2A, 24, 3B, 35, 46, 47, 58, 59, 78, 79, 68, 69. This leaves vertices A and B with degree two. Build two of these graphs and add edges between the corresponding copies of A and B. I really wish you could edit comments. –  Clinton Conley May 11 '11 at 21:43
    
Thanks to all for your nice examples! They illustrate the fact that regularity does not imply symmetry! BTW, it seems that Darij's example is not regular ($X,Y,Z$ being terminal vertices). Let me mention that I just asked a related question on mathoverflow.net/questions/64746/… –  Alain Valette May 12 '11 at 5:25
    
Oh sorry, replace VW, WU, UV by YZ, ZX, XY. It's hard to work with a sketch too small to label the points properly. –  darij grinberg May 12 '11 at 11:32
show 1 more comment

2 Answers

up vote 6 down vote accepted

Counter-example The diameter is 8, but 1 is centered with at most 5 as distance to every other.

share|improve this answer
    
If you have access to sage or other sparse6-format readers, you can get the graph by the given string. sage: g.sparse6_string() ':U___d@C`DecFcFGjAIaJkiLiLMpBObPqoRoRS' –  Pål GD May 11 '11 at 21:55
    
Thanks! And it shows how to extends to higher degree. –  Alain Valette May 12 '11 at 5:07
    
And if you're careful, you can produce a bipartite counterexample, as Darij wanted. –  James Cranch May 12 '11 at 9:23
add comment

Imagine taking a long thin sausage, and drawing four lines from one end to the other end, so that each end of the sausage looks like a cross shape. Then draw a huge number of circles around the sausage.

We've constructed a finite, connected, 4-regular graph. But the diameter is the distance between the endpoints, and the things in the middle of the sausage are genuinely in the middle.

Does that make any sense at all as a counterexample?

A similar construction (where the end of the sausage looks like a hash-sign) gives a bipartite counterexample.

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