The minimum augmentation of a directed tree to a k ‐edge‐connected directed graph

For a directed graph G , let d + (ν) and d (ν) be the outdegree and indegree of vertex ν, respectively. Given a positive integer k , the outdeficiency and indeficiency are defined by δ   k +(ν) = max ( k − d + (ν), 0) and δ   k −(ν) = max( k − d − (ν), 0), respectively. It is evident that in augmenting G to a k ‐edge‐connected directed graph, at least δ k ( G ) = max(Σδ   k +(ν), Σδ   k −(ν)) edges are necessary. This paper proves the theorem that if G is a directed tree (directed graph whose underlying graph is a tree) this number of edges is enough. The proof is made by presenting a construction procedure of polynomial‐order complexity.