Local resilience of graphs
From MaRDI portal
Publication:3608302
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.
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
Cites work
- scientific article; zbMATH DE number 3041944 (Why is no real title available?)
- An algorithm for finding Hamilton paths and cycles in random graphs
- Hamiltonian circuits in random graphs
- On the asymmetry of random regular graphs and random graphs
- On the probability of independent sets in random graphs
- Sandwiching random graphs: universality between random graph models
- Sparse pseudo‐random graphs are Hamiltonian
- The chromatic number of random graphs
- The chromatic number of random graphs
Cited in
(58)- Resilience for the Littlewood-Offord problem
- scientific article; zbMATH DE number 7525473 (Why is no real title available?)
- Corrádi and Hajnal's theorem for sparse random graphs
- Robust Hamiltonicity of random directed graphs
- Recent advances on the Hamiltonian problem: survey III
- Recent progress in combinatorial random matrix theory
- Dirac's theorem for random graphs
- Counting and packing Hamilton cycles in dense graphs and oriented graphs
- Resilience for the Littlewood-Offord problem
- On two Hamilton cycle problems in random graphs
- Local resilience of an almost spanning k‐cycle in random graphs
- The threshold bias of the clique-factor game
- Triangle resilience of the square of a Hamilton cycle in random graphs
- Hamiltonicity in random directed graphs is born resilient
- Bandwidth theorem for random graphs
- Graph Tilings in Incompatibility Systems
- A Dirac-type theorem for Berge cycles in random hypergraphs
- Local resilience and hamiltonicity maker-breaker games in random regular graphs
- Rainbow factors in hypergraphs
- Fixing knockout tournaments with seeds
- Turánnical hypergraphs
- Sandwiching random graphs: universality between random graph models
- On the rank of higher inclusion matrices
- The number of Hamiltonian decompositions of regular graphs
- On the resilience of long cycles in random graphs
- Compatible Hamilton cycles in Dirac graphs
- On the stability of the graph independence number
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Long cycles in subgraphs of (pseudo)random directed graphs
- Compatible Hamilton cycles in random graphs
- Packing trees of unbounded degrees in random graphs
- On the Hamiltonicity of random bipartite graphs
- On coloring resilient graphs
- Hamiltonicity thresholds in Achlioptas processes
- All feedback arc sets of a random Turán tournament have \(\lfloor{n}/{k}\rfloor-{k}+1\) disjoint \({k}\)-cliques (and this is tight)
- On resilience of connectivity in the evolution of random graphs
- Hamiltonicity in random graphs is born resilient
- Characterization of robustness and resilience in graphs: a mini-review
- Tight Hamilton cycles in random hypergraphs
- Long paths and cycles in random subgraphs of graphs with large minimum degree
- Dirac's theorem for random regular graphs
- Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
- On the global strong resilience of fault Hamiltonian graphs
- Robust Hamiltonicity of Dirac graphs
- Generating random graphs in biased maker-breaker games
- Covering cycles in sparse graphs
- A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs
- Independent sets in hypergraphs and Ramsey properties of graphs and the integers
- Dirac-type theorems in random hypergraphs
- When do envy-free allocations exist?
- Robustness of randomized rumour spreading
- Random directed graphs are robustly Hamiltonian
- Packing spanning graphs from separable families
- Resilience with respect to Hamiltonicity in random graphs
- On isomorphism-invariant antistochastic properties of random graphs
- The global resilience of Hamiltonicity in \(G(n, p)\)
- Resilience for tight Hamiltonicity
- Transference for loose Hamilton cycles in random 3-uniform hypergraphs
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)
