Small degree out-branchings

✍ Scribed by Jørgen Bang-Jensen; Stéphan Thomassé; Anders Yeo

• Publisher: John Wiley and Sons
• Year: 2003
• Tongue: English
• Weight: 98 KB
• Volume: 42
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10092

✦ Synopsis

Abstract

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