This may be a something already there in literature but I am unable find it:

Given an undirected simple connected graph $G$ whose vertices has a degree at-least $d$ and $\ge c n^2 $ edges, where $0 < c < 1/2$ is a constant, what is the upper bound on the diameter of $G$?

If this is known, any reference will be appreciated.

  • $\begingroup$ $n$ is the number of vertices of the graph $G$? $\endgroup$ – Alex Ravsky Jun 1 '15 at 5:10

It seems the following.

I shall assume that $n$ is the number of vertices of the graph $G$. The asymptotical upper bound on $\operatorname{diam}(G)$ should be large, $\ge\simeq \frac 2d(1-\sqrt{2c})n.$ To show this, for an arbitrary number $D$ we construct a graph $G$ as follows. Consider a sequence $\{G_0, G_1,\dots, G_D\}$ of mutually disjoint graphs such that $G_0$ is isomorphic to the full graph $K_m$ on $m\ge d\ge 2$ vertices for some $m$ and every of the graphs $G_1,\dots, G_D$ is isomorphic to a graph $K_d$. Put as $G$ the union of all these graphs $G_i$. Since At last, in every $G_i$ pick arbitrary vertices $v_i\ne w_i$ an add to the graph $G$ edges $[v_0,w_1],[v_1, w_2], [v_2, w_3], \dots, [v_{D-1}, w_D]$.

Then $\operatorname{diam}(G)=2D+1,$ every vertex of the graph $G$ has degree at least $d$,


$$e(G)=\frac{m(m-1)}2+D\frac{d(d -1)}2+D.$$


$$e(G)\ge cv(G)^2$$

is equivalent to

$$m^2-m+D(d^2 –d+2)\ge 2c (m+Dd)^2$$

Which yields an asymptotical (with $m\to\infty$ and $d$ fixed) lower bound

$$Dd\ge\simeq\left(\frac 1{\sqrt{2c}}-1\right)m,$$

that is $$D\ge\simeq\frac{1-\sqrt{2c}}{d}n.$$


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.