The intersection of a random geometric graph with an Erdős-Rényi graph
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913573207277568 |
|---|---|
| author | Bennett, Patrick Frieze, Alan Pegden, Wesley |
| author_facet | Bennett, Patrick Frieze, Alan Pegden, Wesley |
| contents | 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) \cap 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)\to 0$ and $r(n)\to 0$; the same model was studied by Kahle, Tian and Wang (2023) for $r(n)\to 0$ but $p$ fixed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04349 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The intersection of a random geometric graph with an Erdős-Rényi graph Bennett, Patrick Frieze, Alan Pegden, Wesley Combinatorics 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) \cap 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)\to 0$ and $r(n)\to 0$; the same model was studied by Kahle, Tian and Wang (2023) for $r(n)\to 0$ but $p$ fixed. |
| title | The intersection of a random geometric graph with an Erdős-Rényi graph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.04349 |