Idioma:

On the asymptotic behavior of the average geodesic distance L and the compactness C.sub.B of simple connected undirected graphs whose order approaches infinity

Lokot, Tatiana ; Abramov, Olga ; Mehler, Alexander

PloS one, 2021-11, Vol.16 (11), p.e0259776 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
On the asymptotic behavior of the average geodesic distance L and the compactness C.sub.B of simple connected undirected graphs whose order approaches infinity
Autor: Lokot, Tatiana ; Abramov, Olga ; Mehler, Alexander
Assuntos: Analysis ; Graph theory
É parte de: PloS one, 2021-11, Vol.16 (11), p.e0259776
Descrição: The average geodesic distance L Newman (2003) and the compactness C.sub.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.sub.B (G), subject to the condition that their order |V(G)| approaches infinity. We prove that the limit of L(G)/n and C.sub.B (G) lies within the interval [0;1/3] and [2/3;1], respectively. Moreover, for any not necessarily rational number [beta] [element of] [0;1/3] ([alpha] [element of] [2/3;1]) we show how to construct the sequence of graphs {G}, |V(G)| = n [right arrow] [infinity], for which the limit of L(G)/n (C.sub.B (G)) is exactly [beta] ([alpha]) (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.
Editor: Public Library of Science
Idioma: Inglês

Voltar para lista de resultados