Bootstrap Percolation on Degenerate Graphs

Marinus Gottschau ()
Additional contact information
Marinus Gottschau: Technical University of Munich

A chapter in Operations Research Proceedings 2017, 2018, pp 303-308 from Springer

Abstract: Abstract In this paper we focus on r-neighbor bootstrap percolation on finite graphs, which is a process on a graph evolving in discrete rounds where, initially, a set $$A_0$$ of vertices gets infected. Now, subsequently, an uninfected vertex becomes infected if it is adjacent to at least r infected vertices. Call $$A_f$$ the set of vertices that are infected after the process stops. More formally, we let $${A_t:=A_{t-1}\cup \{v\in V: |N(v)\cap A_{t-1}|\ge r\}}$$ , where N(v) is the neighborhood of some vertex v. Then $$A_f=\bigcup _{t>0} A_t$$ . We are mainly interested in the size of the final set $$A_f$$ . We present a theorem which bounds the size of the final infected set for degenerate graphs in terms of $$\vert A_0\vert ,d$$ and r. To be more precise, for a d-degenerate graph, if $$r\ge d+1$$ , the size of $$A_f$$ is bounded from above by $$(1+\tfrac{d}{r-d})|A_0|$$ .

Keywords: Bootstrap percolation; Degenerate graphs (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-89920-6_41

Ordering information: This item can be ordered from
http://www.springer.com/9783319899206

DOI: 10.1007/978-3-319-89920-6_41

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().