Small degree out‐branchings

Using a suitable orientation, we give a short proof of a strengthening of a result of Czumaj and Strothmann 4: Every 2‐edge‐connected graph G contains a spanning tree T with the property that $d_T(v)\le {d_T(v)+\,3 \over 2}$ for every vertex v . As an analogue of this result in the directed case, we prove that every 2‐arc‐strong digraph D has an out‐branching B such that $d^+_B(x)\le {d^+_D(x)+ \over 2}+1$ . A corollary of this is that every k ‐arc‐strong digraph D has an out‐branching B such that $d^+_B(v)\le {d^+_D(v)+ \over 2^r}+r$ , where $r=\lfloor \log_2k\rfloor$ . We conjecture that in this case $d^+_B(x)\le {d^+_D(x)+ \over k}+1$ would be the right (and best possible) answer. If true, this would again imply a strengthening of a result from 4 concerning spanning trees with small degrees in k ‐connected graphs when k ≥ 2. We prove that for acyclic digraphs the existence of an out‐branching satisfying prescribed bounds on the out‐degrees of each vertex can be checked in polynomial time. A corollary of this is that the existence of arc‐disjoint branchings $F^+_s$ , $F^-_t$ , where the first is an out‐branching rooted at s and the second an in‐branching rooted at t , can be checked in polynomial time for the class of acyclic digraphs © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 297–307, 2003