<p>Let $G$ be a connected (strongly connected) graph (digraph).</p>

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

<p><strong>What is the maximal diameter possible for such graph?</strong> </p>

<p>For example, if $\delta \geq \frac {n}{2}$ ($\delta^- + \delta^+ \geq n-1)$, <a href="https://cstheory.stackexchange.com/questions/22247/does-deltag-delta-g-geq-n-imply-strong-connectivity/22299#22299">then the graph is of diameter at most 2</a>.</p>

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

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

<p>What other bounds can we get?</p>

CC BY-SA 3.0
2014-05-03T01:17:09.627Z
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.
Chandra Chekuri
CC BY-SA 3.0
2014-05-03T01:49:12.027Z
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).
R B
<graph-theory>
Bound on a graph diameter, considering the minimal vertex degree
R B
# Bound on a graph diameter, considering the minimal vertex degree

(Asked by: username_0 on 2014-05-03)

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](https://cstheory.stackexchange.com/questions/22247/does-deltag-delta-g-geq-n-imply-strong-connectivity/22299#22299).

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?

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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).  

---

## 0 answers

