2
$\begingroup$

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.

  • 1
    This paper might be of interest to $y$ou: http://www.math.ucsd.edu/~fan/mypaps/fanpap/107diameters.pdf2012-04-17

0 Answers 0