guest ::
On the structure of degree vector sets = Über die Struktur von Gradvektormengen
2018 & 2019
Dissertation, RWTH Aachen University, 2018
Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2019
Genehmigende Fakultät
Fak01
Hauptberichter/Gutachter
;
Tag der mündlichen Prüfung/Habilitation
2018-10-26
Online
DOI: 10.18154/RWTH-2018-231996
URL: https://publications.rwth-aachen.de/record/752361/files/752361.pdf
Einrichtungen
Inhaltliche Beschreibung (Schlagwörter)
degree complete graph (frei) ; degree vector (frei) ; orientation (frei) ; out-degree (frei)
Thematische Einordnung (Klassifikation)
DDC: 510
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.In this thesis we consider degree complete graphs. The concept of degree complete graphs was introduced by Qian. An undirected graph is degree complete if its degree vector set can be described as a partially ordered set of integral vectors with respect to a partial order closely related to the dominance order. It turns out that the degree completeness of a graph depends on the considered labeled version of the graph. Qian already noticed this fact and stated the problem to characterize the graphs which possess a degree complete labeled version. Therefore, we give a characterization of graphs which have a degree complete labeling. Further investigations underline that the structure of graphs with degree complete labeling is mainly influenced by the partial order which is used in the definition of degree complete graphs. We consider two classes of partial orders that include the above mentioned partial order. In particular, we study cross-free partial orders (CFPOs) and cone orders. First we extend the concept of degree completeness to the class of cross-free orders and prove that the results on degree complete graphs can be generalized in this sense. Furthermore, we describe the structure of all graphs which are degree complete with respect to a CFPO. Finally, we generalize the concept of degree completeness to all cone orders. A geometric interpretation of our previous results and the structure of degree vector polytopes yield a characterization of those graphs which are degree complete with respect to a cone order.
OpenAccess: 
PDF
(additional files)
Dokumenttyp
Dissertation / PhD Thesis
Format
online
Sprache
English
Externe Identnummern
HBZ: HT019936144
Interne Identnummern
RWTH-2018-231996
Datensatz-ID: 752361
Beteiligte Länder
Germany
|
The record appears in these collections: |