On a classical theorem on the diameter and minimum degree of a graph Articles uri icon

publication date

  • November 2017

start page

  • 1477

end page

  • 1503

issue

  • 11

volume

  • 33

international standard serial number (ISSN)

  • 1439-8516

electronic international standard serial number (EISSN)

  • 1439-7617

abstract

  • 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 Erdos, Pach, Pollack and Tuza. We use these bounds in order to study hyperbolic graphs (in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, delta(0)) be the set of graphs G with n vertices and minimum degree delta(0), and J(n, Delta) be the set of graphs G with n vertices and maximum degree Delta. We study the four following extremal problems on graphs: a(n, delta(0)) = min{delta(G) | G a H(n, delta(0))}, b(n, delta(0)) = max{delta(G) | G a H(n, delta(0))}, alpha(n, Delta) = min{delta(G) | G a J(n, Delta)} and beta(n, Delta) = max{delta(G) | G a J(n, Delta)}. In particular, we obtain bounds for b(n, delta(0)) and we compute the precise value of a(n, delta(0)), alpha(n, Delta) and beta(n, Delta) for all values of n, delta(0) and Delta, respectively.

keywords

  • extremal problems on graphs; diameter; minimum degree; maximum degree; gromov hyperbolicity; hyperbolicity constant; finite graphs