Randomly ordering vertices in graphs has been useful in deriving upper bounds
for the minimal size of contagious sets (where every vertex has threshold
) and lower bounds on the
cardinality of
-degenerate
induced subgraphs. We introduce a new method of randomly picking
permutations from the family of all permutations for which the degree sequence
is either nonincreasing or nondecreasing, and we show that this method
may result in improved bounds for certain graphs for contagious sets or
-degenerate
induced subgraphs. We also reanalyze an algorithm by Reichman for finding
contagious sets and obtain a stronger upper bound on the size of the contagious set
produced by this algorithm.