Abstract
Faults and viruses often spread in networked environments by propagating from site to neighboring sites. We model this process of network contamination by graphs. Consider a graph , whose vertex set is contaminated and our goal is to decontaminate the set using mobile decontamination agents that traverse along the edge set of . Temporal immunity, , is defined as the time that a decontaminated vertex of can remain continuously exposed to some contaminated neighbor without getting infected itself. The immunity number of , , is the least that is required to decontaminate using agents. We study immunity number for some classes of graphs corresponding to network topologies and present upper bounds on , in some cases, with matching lower bounds. Variations of this problem have been extensively studied in literature, but proposed algorithms have been restricted to monotone strategies, where a vertex, once decontaminated, may not be recontaminated. We exploit nonmonotonicity to give bounds which are strictly better than those derived using monotone strategies.