h1

h2

h3

h4

h5
h6
http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png

Independence and k-independence in graphs in terms of degrees = Unabhängigkeit und k-Unabhängigkeit in Graphen in Bezug auf die Gradsequenz



Verantwortlichkeitsangabevorgelegt von Michael Hoschek

ImpressumAachen : Publikationsserver der RWTH Aachen University 2015

UmfangVI, 92 S. : graph. Darst.


Aachen, Techn. Hochsch., Diss., 2015


Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
;

Tag der mündlichen Prüfung/Habilitation
2015-04-17

Online
URN: urn:nbn:de:hbz:82-rwth-2015-018231
URL: https://publications.rwth-aachen.de/record/465864/files/465864.pdf
URL: https://publications.rwth-aachen.de/record/465864/files/465864.pdf?subformat=pdfa

Einrichtungen

  1. Lehrstuhl II für Mathematik (für Ingenieure) (113210)
  2. Fachgruppe Mathematik (110000)

Inhaltliche Beschreibung (Schlagwörter)
Mathematik (frei) ; Graphentheorie (frei) ; Unabhängigkeit (frei) ; Gradsequenz (frei) ; graph theory (frei) ; independence (frei) ; degree seqeuence (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Die Unabhängigkeitszahl eines Graphen ist die Mächtigkeit einer maximalen unabhängigen Menge, d.h. eine Menge aus Knoten, die paarweise nicht miteinander verbunden sind. Für manche spezielle Graphen ist die Unabhängigkeitszahl leicht zu berechnen. Im Allgemeinen gibt es aber keinen effizienten Algorithmus, der diese Invariante in angemessener Zeit berechnet und bildet somit ein fundamentales Problem in der Graphentheorie. Die Bestimmung der Unabängigkeitszahl für allgemeine Graphen ist ein NP-schweres Problem. Neben dem mathematischen Interesse findet die Unabhängigkeitszahl auch in vielen wissenschaftlichen und wirtschaftlichen Problemen ihre Anwendung. Dabei steht die genaue Berechnung solcher Paramter nicht im Vordergrund. Meistens reicht es eine Schranke anzugeben um zu entscheiden, ob ein Prozess durchführbar ist oder nicht. Darin liegt die Motivation, weitere Approximationen für die Unabhängigkeitszahl zu finden und existierende Schranken zu verbessern. Die Approximation der Unabhängigkeitszahl hat den Vorteil, dass nicht alle Informationen eines Graphen benötigt werden. Oft leiten sich die Schranken aus verschiedenen Parametern ab, die einfacher zu handhaben sind. In der vorliegenden Arbeit richten wir den Fokus auf Schranken, die sich aus der Gradsequenz eines Graphen berechnen. Wir haben weiterführende Erkenntnisse über bekannte Schranken und Algorithmen gewonnnen. Dabei lag unser Schwerpunkt bei der Schranke von Owen Murphy aus dem Jahr 1991. Wir haben das Verfahren für spezielle Graphentypen modifiziert und verbessert. Basierend auf dem Murphy Algorithmus haben wir eine neue untere Schranke für die k-Unabhängigkeitszahl entwickelt, welche eine Verallgemeinerung der Unabhängigkeitszahl darstellt. Es gibt Graphen die zeigen, dass unsere neue Approximation in gewissen Fällen eine Verbesserung aller bekannten Schranken ist. Motiviert durch den berühmten Satz von Paul Turán haben wir ein Problem der extremalen Graphentheorie gelöst. Unsere Formel macht eine Aussage über die minimale Anzahl von Kanten, die ein Graph mit gegebener Knotenzahl und k-Unabhängigkeitszahl haben kann. Bei diesen Untersuchungen haben wir einen weiteren Ansatz gefunden, wie man den Algorithmus von Murphy auf k-unabhängige Mengen verallgemeinern kann. Dies führte zu einer zweiten neuen Schranke für bestimmte Graphenklassen, die auch hier zu einer Verbesserung aller bekannten Schranken führte. In Erweiterung unserer Ergebnisse stellt sich in diesem Zusammenhang das Problem, die neue Schranke für allgemeine Graphen zu beweisen. Weder ein Beweis noch ein Gegenbeispiel haben wir fürunsere Hypothese gefunden, so dass die vorliegende Dissertation mit einer Vermutungabschließt.

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.

OpenAccess:
Download fulltext PDF Download fulltext PDF (PDFA)
(additional files)

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
English

Externe Identnummern
HBZ: HT018631389

Interne Identnummern
RWTH-2015-01823
Datensatz-ID: 465864

Beteiligte Länder
Germany

 GO


OpenAccess

QR Code for this record

The record appears in these collections:
Document types > Theses > Ph.D. Theses
Faculty of Mathematics, Computer Science and Natural Sciences (Fac.1) > Department of Mathematics
Publication server / Open Access
Public records
Publications database
113210
110000

 Record created 2015-04-22, last modified 2023-04-08