The minimum augmentation of a directed tree to a k ‐edge‐connected directed graph
Yoji Kajitani, Shuichi Ueno · Networks · 1986
Abstract 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 δ (ν) = max ( k − d + (ν), 0) and δ (ν) = max( k − d − (ν), 0), respectively. It is evident that in augmenting G to a k ‐edge‐connected directed graph, at least δ k ( G ) = max(Σδ (ν), Σδ (ν)) 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.