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.
PDF Access Denied
We have not been able to recognize your IP address
18.97.14.86
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our
journal-recommendation form.
Or, visit our
subscription page
for instructions on purchasing a subscription.