Independence and k-independence in graphs in terms of degrees

  • Unabhängigkeit und k-Unabhängigkeit in Graphen in Bezug auf die Gradsequenz

Hoschek, Michael; Triesch, Eberhard (Thesis advisor); Guo, Yubao (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2015)
Dissertation / PhD Thesis

Aachen, Techn. Hochsch., Diss., 2015


The independence number of a graph is the cardinality of a largest set of vertices such that no two vertices in the set are connected by an edge. The problem of determining a maximum independent set is a fundamental problem in graph theory. Since it is NP-hard for most classes of graphs, approximations in form of lower and upper bounds on the independence number are of specific interest. In addition to the strictly mathematical point of view this graphical invariant appears in several economic and scientific applications. With an appropriate reformulation some practical problems can be interpreted as graphs or networks. The approximation of the decision variables can be sufficient to decide whether a process is feasible or not. Hence the motivation is to investigate further approximations and to improve bounds on the independence number and the generalized k-independence number. The advantage of approximation algorithms is, they do not need all information of a given graph or network. The results often derive from parameters like the order or size of the graph. In this thesis our focus lies on the relation between the independence number and the degree sequence. We have gained many new insights from given results. We modified an algorithm found by Owen Murphy in 1991. This leads to an improvement for graphs which satisfied certain properties and still guarantees a lower bound on the independence number. Our main result is a new lower bound on the k-independence number based on Murphy’s algorithm. For some graphs, our new bound gives a genuine improvement over all known tractable bounds. Motivated by Paul Turàn’s famous theorem, we solved an extremal problem for graphs. Our result makes statements about the minimum size of a graph with given order and k-independence number. It is these considerations which have led to another new lower bound on the k-independence number only under certain conditions. We present graphs for which our result is an improvement over all known bounds. Neither a proof nor a counterexample was found that this result is a bound for arbitrary graphs. Thus we closed our work with a conjecture.