Welcome to MathOverflow

Question

5

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

flag	asked May 11 2011 at 21:17 Alain Valette 6,469●14●26

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 2011 at 21:30

A bipartite counterexample might be more interesting. – darij grinberg May 11 2011 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 2011 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 2011 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 2011 at 11:32

show 1 more comment

Pål GD · Accepted Answer · 2011-05-11 21:53:00Z UTC

6

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

answered May 11 2011 at 21:53

Pål GD
126●1●4

	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 2011 at 21:55
	Thanks! And it shows how to extends to higher degree. – Alain Valette May 12 2011 at 5:07
	And if you're careful, you can produce a bipartite counterexample, as Darij wanted. – James Cranch May 12 2011 at 9:23

James Cranch · Answer 2 · 2011-05-11 21:41:08Z UTC

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.

Realizing the diameter of a finite regular graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.