BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Denote by rg(G,H) the global resilience of a graph G with respect to Hamiltonicity. That is, rg(G,H) is the minimal r for which there exists a subgraph H⊆G with r edges, such that G∖H is not Hamiltonian. We show that if p is above the Hamiltonicity threshold and G∼G(n,p) then, with high probability, rg(G,H)=δ(G)−1. This is easily extended to the full interval: for every p(n)∈[0,1], if G∼G(n,p) then, with high probability, rg(G,H)=max{0,δ(G)−1}.
We study the set L(G) of lengths of all cycles that appear in a random d-regular G on n vertices for a fixed d≥3, as well as in Erdős--Rényi random graphs on n vertices with a fixed average degree c>1. Fundamental results on the distribution of cycle counts in these models were established in the 1980's and early 1990's, with a focus on the extreme lengths: cycles of fixed length, and cycles of length linear in n. Here we derive, for a random d-regular graph, the limiting probability that L(G) simultaneously contains the entire range {ℓ,…,n} for ℓ≥3, as an explicit expression θℓ=θℓ(d)∈(0,1) which goes to 1 as ℓ→∞. For the random graph G(n,p) with p=c/n, where c≥C0 for some absolute constant C0, we show the analogous result for the range {ℓ,…,(1−o(1))Lmax(G)}, where Lmax is the length of a longest cycle in G. The limiting probability for G(n,p) coincides with θℓ from the d-regular case when c is the integer d−1. In addition, for the directed random graph D(n,p) we show results analogous to those on G(n,p), and for both models we find an interval of cε2n consecutive cycle lengths in the slightly supercritical regime p=n1+ε.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.