Local resilience of graphs
From MaRDI portal
Publication:3608302
DOI10.1002/RSA.20235zbMATH Open1182.05114arXiv0706.4104OpenAlexW2953347513WikidataQ105583252 ScholiaQ105583252MaRDI QIDQ3608302FDOQ3608302
Authors: Van Vu, Benny Sudakov 
Publication date: 4 March 2009
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Abstract: In this paper, we initiate a systematic study of graph resilience. The (local) resilience of a graph G with respect to a property P measures how much one has to change G (locally) in order to destroy P. Estimating the resilience leads to many new and challenging problems. Here we focus on random and pseudo-random graphs and prove several sharp results.
Full work available at URL: https://arxiv.org/abs/0706.4104
Recommendations
- On the resilience of long cycles in random graphs
- Local resilience and hamiltonicity maker-breaker games in random regular graphs
- Local resilience of spanning subgraphs in sparse random graphs
- Resilient pancyclicity of random and pseudorandom graphs
- Triangle resilience of the square of a Hamilton cycle in random graphs
Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Sparse pseudo‐random graphs are Hamiltonian
- Title not available (Why is that?)
- Hamiltonian circuits in random graphs
- The chromatic number of random graphs
- The chromatic number of random graphs
- Sandwiching random graphs: universality between random graph models
- An algorithm for finding Hamilton paths and cycles in random graphs
- On the probability of independent sets in random graphs
- On the asymmetry of random regular graphs and random graphs
Cited In (59)
- Transference for loose Hamilton cycles in random 3-uniform hypergraphs
- Resilience for tight Hamiltonicity
- The global resilience of Hamiltonicity in \(G(n, p)\)
- Resilience with respect to Hamiltonicity in random graphs
- Resilience for the Littlewood-Offord problem
- On isomorphism-invariant antistochastic properties of random graphs
- Packing trees of unbounded degrees in random graphs
- On coloring resilient graphs
- Long paths and cycles in random subgraphs of graphs with large minimum degree
- Random directed graphs are robustly Hamiltonian
- Packing spanning graphs from separable families
- Resilience for the Littlewood-Offord problem
- Almost spanning subgraphs of random graphs after adversarial edge removal
- When do envy-free allocations exist?
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Dirac-type theorems in random hypergraphs
- Recent advances on the Hamiltonian problem: survey III
- Covering cycles in sparse graphs
- Dirac's theorem for random regular graphs
- On two Hamilton cycle problems in random graphs
- Hamiltonicity thresholds in Achlioptas processes
- A Dirac-type theorem for Berge cycles in random hypergraphs
- Hamiltonicity in random graphs is born resilient
- Robust Hamiltonicity of random directed graphs
- Turánnical hypergraphs
- Bandwidth theorem for random graphs
- Independent sets in hypergraphs and Ramsey properties of graphs and the integers
- Compatible Hamilton cycles in random graphs
- Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
- On the stability of the graph independence number
- Tight Hamilton cycles in random hypergraphs
- Recent progress in combinatorial random matrix theory
- Generating random graphs in biased maker-breaker games
- The threshold bias of the clique-factor game
- Triangle resilience of the square of a Hamilton cycle in random graphs
- Rainbow factors in hypergraphs
- Long cycles in subgraphs of (pseudo)random directed graphs
- Counting and packing Hamilton cycles in dense graphs and oriented graphs
- On the resilience of long cycles in random graphs
- On the Hamiltonicity of random bipartite graphs
- Corrádi and Hajnal's theorem for sparse random graphs
- Local resilience of an almost spanning k‐cycle in random graphs
- All feedback arc sets of a random Turán tournament have \(\lfloor{n}/{k}\rfloor-{k}+1\) disjoint \({k}\)-cliques (and this is tight)
- Fixing knockout tournaments with seeds
- On the rank of higher inclusion matrices
- The number of Hamiltonian decompositions of regular graphs
- On the global strong resilience of fault Hamiltonian graphs
- Hamiltonicity in random directed graphs is born resilient
- Local resilience and hamiltonicity maker-breaker games in random regular graphs
- Dirac's theorem for random graphs
- On resilience of connectivity in the evolution of random graphs
- A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs
- Robustness of randomized rumour spreading
- Characterization of robustness and resilience in graphs: a mini-review
- Title not available (Why is that?)
- Robust Hamiltonicity of Dirac graphs
- Graph Tilings in Incompatibility Systems
- Sandwiching random graphs: universality between random graph models
- Compatible Hamilton cycles in Dirac graphs
This page was built for publication: Local resilience of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608302)
