Well-balanced orientation

From Egres Open
Jump to: navigation, search

An orientation [math]D=(V,A)[/math] of a graph [math]G=(V,E)[/math] is well-balanced if

[math]\lambda_D(u,v) \geq \left\lfloor \frac{\lambda_G(u,v)}{2}\right\rfloor[/math] for every [math]u,v \in V[/math]

(where [math]\lambda[/math] is the local edge-connectivity). By Nash-Williams' strong orientation theorem, every graph has a well-balanced orientation, and it can be found in polynomial time. We can also satisfy the additional property that [math]\lfloor d_G(v) /2 \rfloor \leq \varrho_D(v) \leq \lceil d_G(v)/2 \rceil [/math]; an orientation with this property is called smooth.