Revan-degree indices on random graphs

Abstract

Given a simple connected non-directed graph $G=(V(G),E(G))$, we consider two families of graph invariants: $R{X}_{\Sigma }(G)={\sum }_{uv\in E(G)}F(r_u,r_v)$ (which has gained interest recently) and $R{X}_{\Pi }(G)={\prod }_{uv\in E(G)}F(r_u,r_v)$ (that we introduce in this work); where $uv$ denotes the edge of $G$ connecting the vertices $u$ and $v$, $r_u$ is the Revan degree of the vertex $u$, and $F$ is a function of the Revan vertex degrees. Here, $r_u=\Delta +\delta -d_u$ with $\Delta$ and $\delta$ the maximum and minimum degrees among the vertices of $G$ and $d_u$ is the degree of the vertex $u$. Particularly, we apply both $R{X}_{\Sigma }(G)$ and R$X_{\Pi }(G)$ on two models of random graphs: Erdös-Rényi graphs and random geometric graphs. By a thorough computational study we show that $⟨R{X}_{\Sigma }(G)⟩$ and $⟨\ln R{X}_{\Pi }(G)⟩$, normalized to the order of the graph, scale with the average Revan degree $⟨r⟩$; here $⟨\cdot ⟩$ denotes the average over an ensemble of random graphs. Moreover, we provide analytical expressions for several graph invariants of both families in the dense graph limit.

16 pages, 10 figures