Project description: Imagine you are in charge of security for an art gallery. Your plan is to post a security guard at certain pieces of art to surveil the gallery. Each guard can see other pieces of art, but only the ones in their line of sight, and they can see the piece of art where they are posted. You want to post guards so that each piece of art is seen by at least two guards, in case one guard is away from their post. But the guards' salaries are expensive, so you want to use the smallest number of guards possible. How to do this?
This problem can be translated to a question in graph theory. Represent each piece of art as a vertex (i.e., a node), and represent each line of sight as an edge. Then the question asks how to identify a special set of vertices such that every vertex is "seen" by at least two vertex in the special set, including possibly itself. The special sets are called double dominating sets. (Technically, if V is the vertex set for the graph G, then a subset D of V is a double dominating set provided that for all v in V the closed neighborhood N[v] contains at least two points of D.)
Finding all the double dominating sets for a given graph is a hard problem, even for trees (NP-complete). This project looks at the question of first identifying all the double dominating sets for certain classes of graphs, e.g., paths, cycles, complete graphs, and complete bipartite graps. Then we will turn our attention to the question of characterizing the trees for which all the minimal double dominating sets have the same size.
Prerequisites: no prerequisite courses; background in graph theory would be an advantage.
Project faculty: