Premium
The minimum augmentation of a directed tree to a k ‐edge‐connected directed graph
Author(s) -
Kajitani Yoji,
Ueno Shuichi
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160207
Subject(s) - combinatorics , mathematics , directed graph , graph , vertex (graph theory) , discrete mathematics , connectivity , edge contraction , strongly connected component , line graph , graph power
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 δ 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.