Asymptotic approximation for the number of n-vertex graphs of given diameter

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)204-214
Number of pages11
JournalJournal of Applied and Industrial Mathematics
Volume11
Issue number2
DOIs
Publication statusPublished - 1 Apr 2017

Keywords

  • graph
  • graph diameter
  • labeled graph
  • number of graphs
  • ordinary graph
  • shortest path

Fingerprint

Dive into the research topics of 'Asymptotic approximation for the number of n-vertex graphs of given diameter'. Together they form a unique fingerprint.

Cite this