An extremal problem: How small scale-free graph can be

Abstract

The bloom of complex network study, in particular, with respect to scale-free ones, is considerably triggering the research of scale-free graph itself. Therefore, a great number of interesting results have been reported in the past, including bounds of diameter. In this paper, we focus mainly on a problem of how to analytically estimate the lower bound of diameter of scale-free graph, i.e., how small scale-free graph can be. Unlike some pre-existing methods for determining the lower bound of diameter, we make use of a constructive manner in which one candidate model ${\mathcal{G}}^{\ast }({\mathcal{V}}^{\ast },{\mathcal{E}}^{\ast })$ with ultra-small diameter can be generated. In addition, with a rigorous proof, we certainly demonstrate that the diameter of graph ${\mathcal{G}}^{\ast }({\mathcal{V}}^{\ast },{\mathcal{E}}^{\ast })$ must be the smallest in comparison with that of any scale-free graph. This should be regarded as the tight lower bound.