The topic of the master's thesis are nonseparating independent sets. We start with the definition of the nonseparating independence number of a graph and its basic properties. We show the connection between nonseparating independent sets and connected vertex covers in graphs. The majority of the thesis is dedicated to the problem of finding the largest nonseparating independent sets (the MaxNSIS problem). First, we show that the problem is solvable in polynomial time for cubic graphs, chordal graphs and hypercubes, after that we deal with the graph families for which the problem is NP-hard. Main result is solving the MaxNSIS problem for Cartesian products of two cycles. Since this problem is closely related to computer science, we will explore algorithms for solving the MaxNSIS problem and their computational complexity in various graphs. As solving this problem has rich applications in everyday life, we will conclude with an overview of these applications.
|
