AUSTRALASIAN JOURNAL OF COMBINATORICS Volume 43 (2009), Pages 91–102 Seepage in directed acyclic graphs

• Main Authors: N. E. Clarke, S. Finbow, S. L. Fitzpatrick
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Subjects: Eldfell; Iceland
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.401.5636

In the firefighting and the graph searching problems, a contaminate spreads relatively quickly. We introduce a new model, on directed acyclic graphs, in which the contamination spreads slowly. The model was inspired by the efforts to stem the lava flow from the Eldfell volcano in Partially supported by grants from NSERC. 92 N.E. CLARKE ET AL. Iceland. The contamination starts at a source, only one vertex at a time is contaminated and for some fixed k, k vertices are protected. The slowness is indicated by the name ‘seepage’. The object is to protect the sinks of the graph. We show that if a sink of the graph can be contaminated then at most one directed path need be contaminated. We also investigate the Cartesian product of directed paths. We show that for the product of 3 directed paths that is truncated to only vertices up to adistanceofdfrom the source, if d ≥ 9, then only one vertex need be protected on each turn to protect the sinks. We also present bounds for the Cartesian product of more than 3 paths. 1