Eindeutige Faktoren von Graphen - maximale Kantenzahlen und Extremalgraphen

Johann, Petra; Triesch, Eberhard

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

Eindeutige Faktoren von Graphen - maximale Kantenzahlen und Extremalgraphen

Johann, Petra (Author)

2000

Verantwortlichkeitsangabevorgelegt von Petra Johann

ImpressumAachen : Publikationsserver der RWTH Aachen University 2000

UmfangVI, 66 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2000

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2000-09-25

Online
URN: urn:nbn:de:hbz:82-opus-569
URL: https://publications.rwth-aachen.de/record/56234/files/Johann_Petra.pdf

Einrichtungen

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

Inhaltliche Beschreibung (Schlagwörter)
Mathematik (frei) ; Graphentheorie (frei) ; Extremalproblem (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Gegeben sei eine feste Knotenmenge V und eine Klasse von Graphen auf V. In der vorliegenden Dissertation wird die folgende, aus dem Gebiet der Suchprobleme stammende Frage untersucht: Wieviele Kanten kann ein Graph auf V Knoten maximal haben, der genau einen Graphen aus der gegebenen Klasse als Teilgraph besitzt? Wie sehen die zugehoerigen extremalen Graphen aus? Diese Frage wird untersucht fuer folgende Klassen: Die Klasse der f-Faktoren auf V, die Klasse der k-regulaeren Graphen auf V, die Klasse der Hamilton-Kreise bzw. Hamilton-Pfade auf V und die Klasse von Graphen auf einer festen kleinen Anzahl von Knoten.

We are given a set V of vertices and a class of graphs on V. In this paper we examine the following question: What is the maximum number of edges in a graph on V, which contains exactly one graph of the class as a subgraph? What can we say about the corresponding extremal graphs? In this thesis we examine graphs with unique f-factors, graphs with unique k-factors, graphs with unique Hamilton cycles or Hamilton paths, and graphs with a unique subgraph on a given (small and fixed) number of edges.

Fulltext:
PDF
(additional files)