New Lower Bounds on the Maximum Number of Minimal Connected Vertex Covers

Abstract

Graphs are important mathematical structures that are used to model many real-life problems. They can, for instance, be used to model relations between objects in a network. An important field of study in graph theory is the study of vertex covers. A vertex cover of a graph is a subset of vertices such that each edge of the graph is incident to at least one vertex in the vertex cover. In this thesis we are interested in listing all vertex covers of a certain type and deciding the maximum number of them. In theoretical computer science we speak about extremal problems where we seek to find how many different configurations of a certain type can occur in a graph, satisfying some properties. Closely related to this, are enumeration problems where the goal is to enumerate all solutions to a given problem. Enumeration of minimal vertex covers are well studied. However, the problem of enumerating minimal connected vertex covers has not been given the same attention. A recent paper by Golovach, Heggernes and Kratsch studies exactly this problem. The authors give an algorithm for enumerating all minimal connected vertex covers in time O(1.8668^n). This also provides an upper bound of 1.8668^n on the number of minimal connected vertex covers a graph can have. They also provide a lower bound, which is a graph that has 3^((n-1)/3) ~ 1.4422^n minimal connected vertex covers. This leaves a gap between the upper and lower bounds. In this thesis we implement and study the algorithm by Golovach et al. We theoretically prove that there exist graphs that have 1.51978^n minimal connected vertex covers. With these discoveries we have been able to increase the lower bound from 1.4422^n to 1.51978^n and by that narrowed the gap between the upper and lower bounds on the number of minimal connected vertex covers in graphs.