Asymptotic approximation for the number of <Emphasis Type="Italic">n</Emphasis>-vertex graphs of given diameter |
| |
Authors: | T I Fedoryaeva |
| |
Institution: | 1.Sobolev Institute of Mathematics,Novosibirsk,Russia;2.Novosibirsk State University,Novosibirsk,Russia |
| |
Abstract: | We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by Füredi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|