On a Classical Theorem on the Diameter and Minimum Degree of a Graph

作     者：Veronica HERNANDEZ Domingo PESTANA Jose M. RODRIGUEZ 

作者机构：Universidad CarlosⅢde MadridAvenida de la Universidad3028911 LeganesSpain 

出 版 物：《Acta Mathematica Sinica,English Series》 (数学学报（英文版）)

年 卷 期：2017年第33卷第11期

页      面：1477-1503页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Supported in part by two grants from Ministerio de Economía y Competitividad Spain:MTM2013-46374-P and MTM2015-69323-REDT 

主　　题：Extremal problems on graphs diameter minimum degree maximum degree Gromov hyperbolicity hyperbolicity constant finite 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 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, δ0） be the set of graphs G with n vertices and minimum degree 50, and J（n, Δ） be the set of graphs G with n vertices and maximum degree A. We study the four following extremal problems on graphs： a（n,δ0） = min{δ（G） ｜ G ∈H（n, δ0）}, b（n, δ0） =- max{δ（G）｜ e ∈H（n, δ0）}, α（n, Δ） = min{δ（G） [ G ∈ J（n, Δ）} and β（n,Δ） = max{δ（G） ] G∈Π（n,Δ）}. In particular, we obtain bounds for b（n, δ0） and we compute the precise value of a（n, δ0）, α（n, Δ） and w（n, Δ） for all values of n, r0 and A, respectively.