Diameter, minimum degree and hyperbolicity constant in graphs

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erdös, Pach, Pollack and Tuza. We use these bounds in order to study hyperbolic graphs (in the Gromov sense). Since computing the hyperbolicity constant is an almost intractable problem, it is natural to try to bound it in terms of some parameters of the graph. Let H(n,δ0) be the set of graphs G with n vertices and minimum degree δ0. We study a(n,δ0):=min⁡{δ(G)|G∈H(n,δ0)} and b(n,δ0):=max⁡{δ(G)|G∈H(n,δ0)}. In particular, we obtain bounds for b(n,δ0) and we compute the precise value of a(n,δ0) for all values of n and δ0.