On the structure of degree vector sets

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

Aachen (2018, 2019) [Doktorarbeit]

Seite(n): 1 Online-Ressource (viii, 141 Seiten) : Illustrationen, Diagramme

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.

Identifikationsnummern

  • REPORT NUMBER: RWTH-2018-231996

Downloads