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^*} (mathcal{V^*}, mathcal{E^*})$ with ultra-small diameter can be generated. In addition, with a rigorous proof, we certainly demonstrate that the diameter of graph $mathcal{G^{*}}(mathcal{V^{*}},mathcal{E^{*}})$ must be the smallest in comparison with that of any scale-free graph. This should be regarded as the tight lower bound.
Download