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)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2018

Abstract

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.