Skip to content
DraconiticResearch
Search Sources API
194,230 studies31 sourcesUpdated 25 min ago
PreprintarXiv licencearXiv

Minimum Weakly Saturated Graphs and Bootstrap Percolation in General Host Graphs

  • Roman Vasquez
Open at sourcePDFDOICite

Abstract

A graph G is weakly H-saturated if one can obtain Kn by adding one edge to G at a time, where each additional edge creates at least one new copy of H. The minimum number of edges needed for a weakly H-saturated graph G of order n is known as the weak saturation number of H, written $wsat(n,H)$. A graph G is minimum weakly saturated if wsat(n,G)=|E(G)|−1 for some value of n. We explore classes of minimum weakly saturated graphs and their connection to the H-bootstrap percolation process, as well as weak saturation in a more general setting than the complete graph.

Related

  1. Stretched exponential asymptotics for bases of triangular bootstrap percolation
    Andrew Elvey Price, Juliette Schabanel, Paul Thévenin
    HALPreprintLicence not statedCombinatorics & discrete mathematicsHAL
  2. Bootstrap percolation on the hypercube
    Fengxing Zhu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  3. 2-Neighbor Bootstrap Percolation on Odd Graphs
    Ali Mohammadian, Sina Rezaie Zareie, Behruz Tayfeh-Rezaie
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  4. Minimum net-saturated graphs of even order
    Xuanyu Cao, Chunxiang Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Seed thresholds and degree variance in heterogeneous bootstrap percolation with growing degrees
    Aleksandr Rodionov
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{vasquez2026minimum,
  title = {{Minimum Weakly Saturated Graphs and Bootstrap Percolation in General Host Graphs}},
  author = {Roman Vasquez},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.01851},
  eprint = {2609.01851},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.01851},
}
RIS
TY  - UNPB
TI  - Minimum Weakly Saturated Graphs and Bootstrap Percolation in General Host Graphs
AU  - Roman Vasquez
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.01851
UR  - https://arxiv.org/abs/2609.01851
AB  - A graph G is weakly H-saturated if one can obtain K_n by adding one edge to G at a time, where each additional edge creates at least one new copy of H. The minimum number of edges needed for a weakly H-saturated graph G of order n is known as the weak saturation number of H, written $wsat(n,H)$. A graph G is minimum weakly saturated if wsat(n,G)=|E(G)|−1 for some value of n. We explore classes of minimum weakly saturated graphs and their connection to the H-bootstrap percolation process, as well as weak saturation in a more general setting than the complete graph.
ER  -