I'm looking for bounds on diameter of a given undirected graph with $n$ vertices and $m$ edges? Formally, I look to find $D_{min}$ and $D_{max}$ such that: $D_{min}\leq Diamter\leq D_{max}$ and it is possible to construct a graph (with $n$ vertices and $m$ edges) satisfying the equalities. A trivial bound is $1\leq Diameter\leq n-1$. Thank you.
Bounds on diameter of a graph
2
$\begingroup$
graph-theory
-
1This paper might be of interest to $y$ou: http://www.math.ucsd.edu/~fan/mypaps/fanpap/107diameters.pdf – 2012-04-17