2
$\begingroup$

I have been thinking a lot on some questions related to centres, diameter ($D$), and radius ($R$) of an undirected connected graph, but couldn't find anywhere the answers, so am posting here.

Ques1. If $x,y$ are two vertices such that distance between them is $D$, then is it true that any shortest path between them will contain at least one centre?

Ques2. If $D=2R$, then does the graph contains only one centre?

Ques3. Also, can we say that if $D<<2R$, then graph would contain a lot of centres? (Intuitively I feel so because in figure below, $D$ is smaller than $2R$, and graph contains a lot of centres, the red coloured vertices.)

$\endgroup$
3
$\begingroup$

A quick way of gaining some confidence or disproving a conjecture is using a computer to generate examples.

For Q1, if $x,y \in V$ such that $d(x,y) = D$, it is not true that any shortest path between $x$ and $y$ contains at least one central vertex (highlighted in red). Here, you can walk from 1 to 6 via 9, 5, and 8 avoiding the red vertex.

enter image description here

For Q2, the answer is also no. Below is a graph whose radius is 2 and diameter is 4. It has 3 central vertices (highlighted in red).

enter image description here

You can use ideas from these counterexamples to optimize the graphs further.

$\endgroup$
  • $\begingroup$ Juho, Thanks a lot. Can you please also tell me any library, or program for quick way of enumerating graphs and verifying the graph questions. Thanks in advance! $\endgroup$ – chyle Jun 27 '18 at 17:40
  • $\begingroup$ @chyle I used Mathematica for finding both of these examples. It is quite fast to use, but not as fast as a raw, custom-made C program for instance. There are tools like that too, you can start by looking at say nauty (and its utility programs). $\endgroup$ – Juho Jun 27 '18 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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