The global resilience of Hamiltonicity in G(n,p)G(n, p)

preprint2023arXivOpen access

Abstract

Denote by rg(G,H)r_g(G,\mathcal{H}) the global resilience of a graph GG with respect to Hamiltonicity. That is, rg(G,H)r_g(G,\mathcal{H}) is the minimal rr for which there exists a subgraph H⊆GH\subseteq G with rr edges, such that G∖HG\setminus H is not Hamiltonian. We show that if pp is above the Hamiltonicity threshold and G∼G(n,p)G\sim G(n,p) then, with high probability, rg(G,H)=δ(G)−1r_g(G,\mathcal{H})=δ(G)-1. This is easily extended to the full interval: for every p(n)∈[0,1]p(n)\in [0,1], if G∼G(n,p)G\sim G(n,p) then, with high probability, rg(G,H)=max⁡{0,δ(G)−1}r_g(G,\mathcal{H})= \max \{ 0,δ(G)-1 \}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.