% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@PHDTHESIS{Hoschek:465864,
author = {Hoschek, Michael},
othercontributors = {Triesch, Eberhard and Guo, Yubao},
title = {{I}ndependence and k-independence in graphs in terms of
degrees},
school = {Aachen, Techn. Hochsch.},
type = {Dissertation},
address = {Aachen},
publisher = {Publikationsserver der RWTH Aachen University},
reportid = {RWTH-2015-01823},
pages = {VI, 92 S. : graph. Darst.},
year = {2015},
note = {Aachen, Techn. Hochsch., Diss., 2015},
abstract = {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.},
cin = {113210 / 110000},
ddc = {510},
cid = {$I:(DE-82)113210_20140620$ / $I:(DE-82)110000_20140620$},
typ = {PUB:(DE-HGF)11},
urn = {urn:nbn:de:hbz:82-rwth-2015-018231},
url = {https://publications.rwth-aachen.de/record/465864},
}
guest ::