Orientations of Graphs and Minimum Degrees of Graphs

Abstract

Katerinis established the following result in [1]. Let \(G\) be a simple graph with \(\delta(G) \geq \lfloor\frac{|V(G)|}{2}+k\), where \(k\) is a non-negative integer. Let \(f : V(G) \to \mathbb{Z}^+\) be a function having the following properties:

(1) \(\frac{1}{2}\left({d_G(v) – (k+1)}{2}\right) \leq f(v) \leq \frac{1}{2}\left({d_G(v) + (k+1)}{2}\right)\) for every \(v \in V(G)\),

(2) \(\sum_{v\in V(G)} f(v) = |E(G)|\).

Then \(G\) has an orientation \(D\) such that \(d^+_D(v) = f(v)\), for every \(v \in V(G)\). In this paper, we focus on the sharpness of the above two inequalities.