Dr. Sebastian Milz

Kontakt / Veröffentlichungen / Vorträge / Lehre


[2013] [2017]
Connectivity of local tournaments
Connectivity of local tournaments

abstract not available
22nd Workshop on Cycles and Colourings, Novy Smokovec, High Tatras, Slovakia. (09/09/2013)

Degree complete graphs
Degree complete graphs

Let G=(V,E) be a graph with an ordered vertex set V=\{1,\ldots,n\}. We call a vector of nonnegative integers S=(s_1,\ldots,s_n) a degree vector of G if there is an orientation D of G such that s_i=d^+_D(i) for all i\in V. It is known that every degree vector satisfies S_G^l\preceq S \preceq S_G^r,\quad \sum_{i=1}^n{s_i}=|E| and 0\le s_i\le d_G(i) for all i=1,\ldots,n, (1) where S_G^l (S_G^r) is the minimal (maximal) degree vector of G with respect to the domination order. The graph G is called degree complete if every vector s satisfying condition (1) is a degree vector of G. In 2006 Qian characterized degree complete graphs with ordered vertex sets. Suppose we are given a graph G without an ordered vertex set Qian asked how to decide whether there is an ordering of the vertices of G that yields a degree complete graph. Answering this problem we give two characterizations of the class of graphs which have such a degree complete vertex set ordering. Moreover we state a polynomial procedure to find a desired ordering of the vertices of G if it exsists.
49th Southeastern International Conference on Combinatorics, Graph Theory & Computing, Boca Raton, Florida, USA. (03/06/2017)

letzte Änderung: 09.12.2018 - 11:59