2024/11/07 by Patrick Bennett, Alan Frieze, Bennett, Patrick +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Mathematics #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2411.04349
openalex publication_date 2024/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the intersection of a random geometric graph with an Erdős-Rényi graph. Specifically, we generate the random geometric graph G(n, r) by choosing n points uniformly at random from D=[0, 1]2 and joining any two points whose Euclidean distance is at most r. We let G(n, p) be the classical Erdős-Rényi graph, i.e. it has n vertices and every pair of vertices is adjacent with probability p independently. In this note we study G(n, r, p):=G(n, r) ∩ G(n, p). One way to think of this graph is that we take G(n, r) and then randomly delete edges with probability 1-p independently. We consider the clique number, independence number, connectivity, Hamiltonicity, chromatic number, and diameter of this graph where both p(n)→ 0 and r(n)→ 0; the same model was studied by Kahle, Tian and Wang (2023) for r(n)→ 0 but p fixed.