Regular factors in graphs

Hoffmann, Arne; Volkmann, Lutz

doi:urn:nbn:de:hbz:82-opus-3897

Regular factors in graphs

Hoffmann, Arne (Author)

2002

Verantwortlichkeitsangabevorgelegt von Arne Hoffmann

ImpressumAachen : Publikationsserver der RWTH Aachen University 2002

UmfangV, 70 S.

Aachen, Techn. Hochsch., Diss., 2002

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Volkmann, Lutz (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2002-07-12

Online
URN: urn:nbn:de:hbz:82-opus-3897
URL: https://publications.rwth-aachen.de/record/57026/files/Hoffmann_Arne.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Mathematik (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Der erste Teil dieser Arbeit untersucht den Einfluss verschiedener Graphenparameter auf die Existenz eines regulaeren Faktors in einem regulaeren Graphen. Es werden scharfe hinreichende Bedingungen fuer die Existenz eines regulaeren Faktors bewiesen, falls neben der Ordnung und dem Grad des Graphen der Radius, die chromatische Zahl oder der Eckenzusammenhang bekannt sind. Der zweite Teil dieser Arbeit beschaeftigt sich mit der Fragestellung, wieviele Kanten ein Graph maximal besitzen kann, wenn er einen eindeutigen regulaeren Faktor enthaelt. In der vorliegenden Dissertation liegt der Schwerpunkt bei extremalen bipartiten Graphen mit einem eindeutigen regulaeren Faktor. Eine Strukturanalyse zeigt, dass die extremalen Graphen genau 2k Ecken vom Grad k besitzen, wenn der Graph einen eindeutigen k-Faktor enthaelt. Fuer kleine k ermoeglicht dies Aussagen ueber die maximale Kantenzahl. Abschliessend werden in der Arbeit extremale Graphen mit einem eindeutigen [1,k]-Faktor betrachtet.

The first part of this dissertation deals with the influence of different parameters on the existence of a regular factor in a regular graph. Sharp sufficient conditions for the existence of a regular factor are presented, if either the radius, the chromatic number or the vertex-connectivity of the graph are known, besides the order and the degree of the graph. The second part deals with the question how large the edge-set of a graph can be if the graph has a unique regular factor. The focus will be on extremal bipartite graphs with a unique regular factor. An analysis of the structure shows that all extremal bipartite graphs with a unique k-factor have exactly 2k vertices of minimum degree. This result allows for positive answers on the maximal number of edges in an extremal graph if k is small. This dissertation closes with results on extremal graphs with a unique [1,k]-factor.

Fulltext:
PDF
(additional files)