On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs

preprint2011arXivOpen access

Abstract

Let $\bk=(k_1,...,k_n)$ be a sequence of nn integers. For an increasing monotone graph property $\mP$ we say that a base graph G=([n],E)G=([n],E) is \emph{$\bk$-resilient} with respect to $\mP$ if for every subgraph H⊆GH\subseteq G such that dH(i)≤kid_H(i)\leq k_i for every 1≤i≤n1\leq i\leq n the graph G−HG-H possesses $\mP$. This notion naturally extends the idea of the \emph{local resilience} of graphs recently initiated by Sudakov and Vu. In this paper we study the $\bk$-resilience of a typical graph from $\GNP$ with respect to the Hamiltonicity property where we let pp range over all values for which the base graph is expected to be Hamiltonian. In particular, we prove that for every ε>0ε>0 and p≥ln⁡n+ln⁡ln⁡n+ω(1)np\geq\frac{\ln n+\ln\ln n +ω(1)}{n} if a graph is sampled from $\GNP$ then with high probability removing from each vertex of "small" degree all incident edges but two and from any other vertex at most a (13−ε)(\frac{1}{3}-ε)-fraction of the incident edges will result in a Hamiltonian graph. Considering this generalized approach to the notion of resilience allows to establish several corollaries which improve on the best known bounds of Hamiltonicity related questions. It implies that for every positive ε>0ε>0 and large enough values of KK, if p>Kln⁡nnp>\frac{K\ln n}{n} then with high probability the local resilience of $\GNP$ with respect to being Hamiltonian is at least (1−ε)np/3(1-ε)np/3, improving on the previous bound for this range of pp. Another implication is a result on optimal packing of edge disjoint Hamilton cycles in a random graph. We prove that if p≤1.02ln⁡nnp\leq\frac{1.02\ln n}{n} then with high probability a graph GG sampled from $\GNP$ contains ⌊δ(G)2⌋\lfloor\frac{δ(G)}{2}\rfloor edge disjoint Hamilton cycles, extending the previous range of pp for which this was known to hold.

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.