Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2209.05677 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909677738000384 |
|---|---|
| author | Dabirian, Hossein Subramanian, Vijay |
| author_facet | Dabirian, Hossein Subramanian, Vijay |
| contents | Bilateral agreement based random undirected graphs were introduced and analyzed by La and Kabkab in 2015. The construction of the graph with $n$ vertices in this model uses a (random) preference order on other $n-1$ vertices and each vertex only prefers the top $k$ other vertices using its own preference order; in general, $k$ can be a function of $n$. An edge is constructed in the ensuing graph if and only if both vertices of a potential edge prefer each other. This random graph is a generalization of the random $k^{th}$-nearest neighbor graphs of Cooper and Frieze that only consider unilateral preferences of the vertices. Moharrami \emph{et al.} studied the emergence of a giant component and its size in this new random graph family in the limit of $n$ going to infinity when $k$ is finite. Connectivity properties of this random graph family have not yet been formally analyzed. In their original paper, La and Kabkab conjectured that for $k(t)=t \log n$, with high probability connectivity happens at $t>1$ and the graph is disconnected for $t<1$. We provide a proof for this conjecture. We will also introduce an asymptotic for the average degree of this graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_05677 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Connectivity of a Family of Bilateral Agreement Random Graphs Dabirian, Hossein Subramanian, Vijay Probability Combinatorics Bilateral agreement based random undirected graphs were introduced and analyzed by La and Kabkab in 2015. The construction of the graph with $n$ vertices in this model uses a (random) preference order on other $n-1$ vertices and each vertex only prefers the top $k$ other vertices using its own preference order; in general, $k$ can be a function of $n$. An edge is constructed in the ensuing graph if and only if both vertices of a potential edge prefer each other. This random graph is a generalization of the random $k^{th}$-nearest neighbor graphs of Cooper and Frieze that only consider unilateral preferences of the vertices. Moharrami \emph{et al.} studied the emergence of a giant component and its size in this new random graph family in the limit of $n$ going to infinity when $k$ is finite. Connectivity properties of this random graph family have not yet been formally analyzed. In their original paper, La and Kabkab conjectured that for $k(t)=t \log n$, with high probability connectivity happens at $t>1$ and the graph is disconnected for $t<1$. We provide a proof for this conjecture. We will also introduce an asymptotic for the average degree of this graph. |
| title | Connectivity of a Family of Bilateral Agreement Random Graphs |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2209.05677 |