Open AccessOn the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity
Author(s) -
Tatiana Lokot,
Olga Abramov,
Alexander Mehler
Publication year - 2021
Publication title -
plos one
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.99
H-Index - 332
ISSN - 1932-6203
DOI - 10.1371/journal.pone.0259776
Subject(s) - combinatorics , geodesic , compact space , mathematics , connectivity , limit point , simple (philosophy) , limit (mathematics) , order (exchange) , infinity , discrete mathematics , undirected graph , graph , pure mathematics , mathematical analysis , philosophy , epistemology , finance , economics
The average geodesic distance L Newman (2003) and the compactness C B Botafogo (1992) are important graph indices in applications of complex network theory to real-world problems. Here, for simple connected undirected graphs G of order n , we study the behavior of L ( G ) and C B ( G ), subject to the condition that their order | V ( G )| approaches infinity. We prove that the limit of L ( G )/ n and C B ( G ) lies within the interval [0;1/3] and [2/3;1], respectively. Moreover, for any not necessarily rational number β ∈ [0;1/3] ( α ∈ [2/3;1]) we show how to construct the sequence of graphs { G }, | V ( G )| = n → ∞, for which the limit of L ( G )/ n ( C B ( G )) is exactly β ( α ) (Theorems 1 and 2). Based on these results, our work points to novel classification possibilities of graphs at the node level as well as to the information-theoretic classification of the structural complexity of graph indices.