On the local resilience of random geometric graphs with respect to connectivity and long cycles

• Published in: arXiv.org 2024-06
• Main Authors: Alberto Espuny Díaz, Lichev, Lyuben, Wesolek, Alexandra
• Format: Article
• Language: English
• Subjects: Apexes; Connectivity; Graph theory; Graphs; Resilience
• ISSN: 2331-8422

Given an increasing graph property \(\mathcal{P}\), a graph \(G\) is \(\alpha\)-resilient with respect to \(\mathcal{P}\) if, for every spanning subgraph \(H\subseteq G\) where each vertex keeps more than a \((1-\alpha)\)-proportion of its neighbours, \(H\) has property \(\mathcal{P}\). We study the above notion of local resilience with \(G\) being a random geometric graph \(G_d(n,r)\) obtained by embedding \(n\) vertices independently and uniformly at random in \([0,1]^d\), and connecting two vertices by an edge if the distance between them is at most \(r\). First, we focus on connectivity. We show that, for every \(\varepsilon>0\), for \(r\) a constant factor above the sharp threshold for connectivity \(r_c\) of \(G_d(n,r)\), the random geometric graph is \((1/2-\varepsilon)\)-resilient for the property of being \(k\)-connected, with \(k\) of the same order as the expected degree. However, contrary to binomial random graphs, for sufficiently small \(\varepsilon>0\), connectivity is not born \((1/2-\varepsilon)\)-resilient in \(2\)-dimensional random geometric graphs. Second, we study local resilience with respect to the property of containing long cycles. We show that, for \(r\) a constant factor above \(r_c\), \(G_d(n,r)\) is \((1/2-\varepsilon)\)-resilient with respect to containing cycles of all lengths between constant and \(2n/3\). Proving \((1/2-\varepsilon)\)-resilience for Hamiltonicity remains elusive with our techniques. Nevertheless, we show that \(G_d(n,r)\) is \(\alpha\)-resilient with respect to Hamiltonicity for a fixed constant \(\alpha = \alpha(d)