On the structure of degree vector sets

• Über die Struktur von Gradvektormengen

Milz, Sebastian Horst Ignaz; Triesch, Eberhard (Thesis advisor); Schaudt, Oliver (Thesis advisor)

Aachen (2018, 2019)
Doktorarbeit

Dissertation, RWTH Aachen University, 2018

Kurzfassung

In der vorliegenden Dissertation betrachten wir gradvollständige Graphen. Dieses Konzept wurde von Qian eingeführt. Ein ungerichteter Graph ist gradvollständig, falls seine Gradvektormenge mit Hilfe einer aus der Dominanzordnung abgeleiteten Halbordnung dargestellt werden kann. Es zeigt sich, dass die Eigenschaft der Gradvollständigkeit eines Graphen davon abhängig ist, welche gelabelte Version des Graphen betrachtet wird. Diese Tatsache wurde bereits von Qian erkannt und als Problemstellung formuliert. Aus diesem Grund charakterisieren wir als erstes alle Graphen, die ein sogenanntes gradvollständiges Label besitzen. Weitere Untersuchungen zeigen, dass die Struktur der Graphen mit gradvollständigem Label in einem engen Zusammenhang zu der Halbordnung steht, die in der Definition der gradvollständigen Graphen benutzt wurde. Im weiteren Verlauf der Arbeit betrachten wir zwei Klassen von Halbordnungen, welche die oben erwähnte Halbordnung enthalten. Konkret untersuchen wir kreuzungsfreie Halbordnungen und Kegelordnungen. Zuerst erweitern wir das Konzept der Gradvollständigkeit auf die Klasse der kreuzungsfreien Halbordnungen und zeigen wie sich die Resultate der gradvollständigen Graphen in dieser Hinsicht verallgemeinern lassen. Außerdem beschreiben wir die Struktur der Graphen, die gradvollständig bzgl. einer kreuzungsfreien Halbordnung sind. Schließlich erweitern wir das Konzept der gradvollständigen Graphen auf alle Kegelordnungen. Dazu interpretieren wir unter anderem die vorangegangenen Ergebnisse aus einer geometrischen Perspektive. Zusätzlich charakterisieren wir alle Graphen, die bzgl. einer Kegelordnung gradvollständig sind. Dazu verwenden wir Kenntnisse über die Polytope, welche sich als konvexe Hülle der Gradvektormenge der gegebenen Graphen ergeben.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehrstuhl II für Mathematik (für Ingenieure) [113210]