Computational and analytical studies of the Randi¿ index in Erdös-Rényi models Articles uri icon

publication date

  • July 2020

start page

  • 125137-1

end page

  • 125137-14

volume

  • 377

International Standard Serial Number (ISSN)

  • 0096-3003

Electronic International Standard Serial Number (EISSN)

  • 1873-5649

abstract

  • In this work we perform computational and analytical studies of the Randić index R(G) in Erdös-Rényi models G(n,p) characterized by n vertices connected independently with probability p epsilon (0, 1). First, from a detailed scaling analysis, we show that 〈R(G)〉=〈R(G)〉/(n/2) scales with the product xi≈np, so we can define three regimes: a regime of mostly isolated vertices when xi< 0.01 (R(G) ≈0), a transition regime for 0.01 < xi< 10 (where 0 < R(G) < n/2), and a regime of almost complete graphs for xi> 10 (R(G) ≈n/2). Then, motivated by the scaling of 〈R(G)〉, we analytically (i) obtain new relations connecting R(G) with other topological indices and characterize graphs which are extremal with respect to the relations obtained and (ii) apply these results in order to obtain inequalities on R(G) for graphs in Erdös-Rényi models.

keywords

  • randic index; vertex-degree-based topological; index random graphs; erdös-rényi graphs