2024/06/14 by Alberto Espuny Díaz, Díaz, Alberto Espuny, Lyuben Lichev +3
Computer Science · #Interconnection Networks and Systems #Mobile Ad Hoc Networks #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2406.09921
Given an increasing graph property P, a graph G is α-resilient with respect to P if, for every spanning subgraph H⊆ G where each vertex keeps more than a (1-α)-proportion of its neighbours, H has property P. We study the above notion of local resilience with G being a random geometric graph Gd(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 ε>0, for r a constant factor above the sharp threshold for connectivity rc of Gd(n,r), the random geometric graph is (1/2-ε)-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 ε>0, connectivity is not born (1/2-ε)-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 rc, Gd(n,r) is (1/2-ε)-resilient with respect to containing cycles of all lengths between constant and 2n/3. Proving (1/2-ε)-resilience for Hamiltonicity remains elusive with our techniques. Nevertheless, we show that Gd(n,r) is α-resilient with respect to Hamiltonicity for a fixed constant α= α(d)<1/2.