3
$\begingroup$

Let $G$ be a connected (strongly connected) graph (digraph).

Assume that the minimal vertex degree (in/out degrees) of the graph is $\delta$ (are $\delta^-,\delta^+$).

What is the maximal diameter possible for such graph?

For example, if $\delta \geq \frac {n}{2}$ ($\delta^- + \delta^+ \geq n-1)$, then the graph is of diameter at most 2.

Also, it seems that $\delta \geq c\cdot n$ gives an upper bound of $\lceil \frac{2}{c} \rceil - 1$ on the diameter, but I'm not sure it's tight (also, haven't tried proving it yet, so I might be wrong).

(For $c=\frac{1}{2}$ it's definitely not tight).

What other bounds can we get?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ One can show directed graphs that have diameter $\Omega(n)$ and $\delta^-$ and $\delta^+$ are both $\Omega(n)$. For undirected graphs one can show that the diameter is $O(n/\delta)$. These are fairly simple exercises. $\endgroup$ – Chandra Chekuri May 3 '14 at 1:17
  • $\begingroup$ Thanks @ChandraChekuri. The undirected bound you've mentioned was exactly ( up to a constant factor ) what I expected, but I think the constants are interesting too (as well as in the directed case). $\endgroup$ – R B May 3 '14 at 1:49

Your Answer

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

Browse other questions tagged or ask your own question.