Back to Search
Start Over
On fractional fragility rates of graph classes
- Source :
- The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics, Open Journal Systems, 2020, 27 (4), ⟨10.37236/8909⟩, The Electronic Journal of Combinatorics, 2020, 27 (4), ⟨10.37236/8909⟩
- Publication Year :
- 2019
-
Abstract
- We consider, for every positive integer $a$, probability distributions on subsets of vertices of a graph with the property that every vertex belongs to the random set sampled from this distribution with probability at most $1/a$. Among other results, we prove that for every positive integer $a$ and every planar graph $G$, there exists such a probability distribution with the additional property that for any set $X$ in the support of the distribution, the graph $G-X$ has component-size at most $(\Delta(G)-1)^{a+O(\sqrt{a})}$, or treedepth at most $O(a^3\log_2(a))$. We also provide nearly-matching lower bounds.
- Subjects :
- Combinatorics
Fragility
Computational Theory and Mathematics
Applied Mathematics
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Discrete Mathematics and Combinatorics
Graph (abstract data type)
Mathematics - Combinatorics
Geometry and Topology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Theoretical Computer Science
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 10778926
- Database :
- OpenAIRE
- Journal :
- The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics, Open Journal Systems, 2020, 27 (4), ⟨10.37236/8909⟩, The Electronic Journal of Combinatorics, 2020, 27 (4), ⟨10.37236/8909⟩
- Accession number :
- edsair.doi.dedup.....bde02ac6b6dcf7c47dcc10c924aedbd6
- Full Text :
- https://doi.org/10.37236/8909⟩