Grant: Discovery Grants Program - Individual

Graph searching models often use the metaphor of decontaminating a network. For example, consider a network of pipes with a regenerating biological contaminant that is mobile so that contamination can spread from one area to another. Mobile agents are used to clean the network. Of particular interest in this proposal is the situation where the network has to be cleaned regularly because of a slow growing contaminant, such as algae or zebra mussels. My goals are to analyze these graph searching and cleaning models and establish relationships to other problems and applications. Another model considers the spread of fire on a network with a limited number of firefighters available to protect regions of the network. At each time step, the fire spreads and a firefighter is able to protect (for perpetuity) a region of the network. Part of my proposal is to determine the maximum percentage of nodes on a network that can be saved from the fire; specifically I wish to work on some conjectures regarding particular infinite grids. As well, I propose to examine the problem when the fire is restricted to spreading, at each time step, to a maximum of k nodes.Due to the popularity of on-line social networks such as Facebook and Twitter, data about social interactions in on-line social networks has become readily available. This has prompted the introduction of various models for on-line social networks. I plan to examine some graph searching parameters for the models. One can easily interpret the spread of fire as the spread of malicious gossip, for example. I also propose to investigate various other graph parameters in terms of these on-line social network models, in an attempt to learn more about their structures.