Connectivity of local tournaments

abstract not available

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.