Project description: Imagine you are in charge of security for an art gallery. Your plan is to install a security camera at certain pieces of art to surveil the gallery. Each camera can see other pieces of art, but only the ones in its line of sight, and not the piece of art where it is positioned. You want to place cameras so that each piece of art is seen by at least one camera. But the cameras are expensive, so you want to use the smallest number of cameras 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 in the graph is adjacent to at least one vertex in the special set. The special sets are called total dominating sets.
Finding all the total 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 total 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 total dominating sets have the same size.
Check out the introductory video for this project.
Prerequisites: no prerequisite courses; background in graph theory would be an advantage.
Project faculty: