Largest and smallest minimal percolating sets in trees (Q426841)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Largest and smallest minimal percolating sets in trees
scientific article

    Statements

    Largest and smallest minimal percolating sets in trees (English)
    0 references
    0 references
    12 June 2012
    0 references
    Summary: Originally introduced by \textit{J. Chalupa}, \textit{P.L. Leath} and \textit{G.R. Reich} [``Bootstrap percolation on a Bethe lattice'', J. Phys. C., 12, L31--L35, (1979)] for use in modeling disordered magnetic systems, \(r\)-bootstrap percolation is the following deterministic process on a graph. Given an initial infected set, vertices with at least \(r\) infected neighbors are infected until no new vertices can be infected. A set percolates if it infects all the vertices of the graph, and a percolating set is minimal if no proper subset percolates. We consider minimal percolating sets in finite trees. We show that if \(A\) is a minimal percolating set on a tree \(T\) with \(n\) vertices and \(\ell\) vertices of degree less than \(r\) (leaves in the case \(r=2\)), then \(\frac{(r-1)n+1}{r} \leq |A| \leq \frac{rn+\ell}{r+1}\). Moreover, we show that the difference between the sizes of a largest and smallest minimal percolating sets is at most \(\frac{(r-1)(n-1)}{r^2}\). Finally, we describe \(O(n)\) algorithms for computing the largest (for \(r=2\)) and smallest (for \(r \geq 2\)) minimal percolating sets.
    0 references
    percolation
    0 references
    graph theory
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references