2022/10/10 by R. Aguilar-Sanchez, Aguilar-Sanchez, R., I. F. Herrera-González +5 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2210.04749
openalex publication_date 2022/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a simple connected non-directed graph G=(V(G),E(G)), we consider two families of graph invariants: RXΣ(G) = ∑uv ∈ E(G) F(ru,rv) (which has gained interest recently) and RXΠ(G) = ∏uv ∈ E(G) F(ru,rv) (that we introduce in this work); where uv denotes the edge of G connecting the vertices u and v, ru is the Revan degree of the vertex u, and F is a function of the Revan vertex degrees. Here, ru = Δ+ δ- du with Δ and δ the maximum and minimum degrees among the vertices of G and du is the degree of the vertex u. Particularly, we apply both RXΣ(G) and RXΠ(G) on two models of random graphs: Erdös-Rényi graphs and random geometric graphs. By a thorough computational study we show that < RXΣ(G) > and < ln RXΠ(G) >, normalized to the order of the graph, scale with the average Revan degree < r >; here < ⋅ > 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.