FAQ
© 2016 Staats- und Universitätsbibliothek
Hamburg, Carl von Ossietzky

Öffnungszeiten heute09.00 bis 24.00 Uhr alle Öffnungszeiten

Eingang zum Volltext in OPUS

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:gbv:18-81825
URL: http://ediss.sub.uni-hamburg.de/volltexte/2016/8182/


Structural properties of dense graphs with high odd girth and packing of minor-closed families of graphs

Struktur dichter Graphen mit hoher Taillenweite und Packungen unter Minorenbildung abgeschlossener Graphenfamilien

Messuti, Silvia

pdf-Format:
 Dokument 1.pdf (1.513 KB) 


Basisklassifikation: 31.12
Institut: Mathematik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Hauptberichter: Schacht, Mathias (Prof. PhD)
Sprache: Englisch
Tag der mündlichen Prüfung: 07.07.2016
Erstellungsjahr: 2016
Publikationsdatum: 16.11.2016
Kurzfassung auf Englisch: We present two results that concern different aspects of extremal graph theory.
In the first part we study minimum degree conditions for which a graph with given odd girth is homomorphic to its smallest odd cycle. This is motivated by a classical result of Andrásfai, Erdős, and Sós which states that every n-vertex graph with odd girth at least 2k+1 and minimum degree larger than 2n/(2k+1) is bipartite. Since the cycle of length 2k+1 is an extremal graph for this problem, we asked whether a weaker degree condition implies the existence of a homomorphism into C_(2k+1). We show that this happens for any n-vertex graph with odd girth 2k+1 and minimum degree larger than 3n/4k and give a detailed description of the extremal graphs.
The second part of our work is dedicated to a packing problem that has its roots in Gyárfás’ Tree Packing Conjecture. This conjecture states that a sequence of n trees (T_1, ..., T_n) with v(T_i)=i packs into K_n. An asymptotic version of this conjecture in which trees with bounded maximum degree are packed into K_(1+o(1))n was recently proved. We generalise this result from sequences of trees to sequences of graphs from any non-trivial minor-closed class.
Kurzfassung auf Deutsch: Wir stellen zwei Ergebnisse vor, die verschiedene Aspekte der extremalen Graphentheorie betreffen.
Im ersten Teil untersuchen wir Minimalgradbedingungen für die ein Graph mit gegebener ungerader Taillenweite homomorph zu dem kleinsten ungeraden Kreis ist, den er enthält. Diese Frage ist durch ein Resultat von Andrásfai, Erdős, und Sós motiviert, welches besagt, dass jeder Graph auf n Ecken mit ungerader Taillenweite mindestens 2k+1 und Minimalgrad größer als 2n/(2k+1) bipartit ist. Da der Kreis auf 2k+1 Ecken ein extremaler Graph für dieses Problem ist, untersuchen wir ob eine schwächere Minimalgradbedingung die Existenz eines Homomorphismus in C_(2k+1) impliziert. Wir zeigen, dass dies für Graphen auf n Ecken mit ungerader Taillenweite 2k+1 und Minimalgrad größer als 3n/4k gilt und beschreiben die extremalen Graphen im Detail.
Im zweiten Teil untersuchen wir ein Packungsproblem, dass seinen Ursprung in der Baumpackungsvermutung von Gyárfás hat. Diese Vermutung besagt, dass jede Folge von Bäumen (T_1, ..., T_n) mit v(T_i)=i sich in den K_n packen lässt. Eine asymptotische Variante dieser Vermutung, in der Bäume mit beschränktem Maximalgrad in K_(1+o(1))n gepackt werden, wurde kürzlich gezeigt. Wir verallgemeinern dieses Resultat auf Folgen von Graphen mit beschränktem Maximalgrad aus jeder beliebigen nicht-trivialen unter Minorenbildung abgeschlossenen Graphenklasse.

Zugriffsstatistik

keine Statistikdaten vorhanden
Legende