dc.contributor.author Ryland, Ida dc.date.accessioned 2017-06-22T10:29:37Z dc.date.available 2017-06-22T10:29:37Z dc.date.issued 2017-06-20 dc.date.submitted 2017-06-19T22:00:12Z dc.identifier.uri https://hdl.handle.net/1956/16055 dc.description.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. en_US dc.language.iso eng eng dc.publisher The University of Bergen en_US dc.subject Enumeration eng dc.subject minimal connected vertex covers eng dc.subject upper bound eng dc.subject lower bound eng dc.title New Lower Bounds on the Maximum Number of Minimal Connected Vertex Covers en_US dc.type Master thesis dc.date.updated 2017-06-19T22:00:12Z dc.rights.holder Copyright the Author. All rights reserved en_US dc.description.degree Masteroppgave i informatikk en_US dc.description.localcode INF399 dc.subject.nus 754199 eng fs.subjectcode INF399 fs.unitcode 12-12-00
﻿