Minimal

Let G be a graph and let T be a tree with the same vertex set. Let e be an edge of T and Ae and Be be the vertex sets of the components of T obtained after removal of e. Let EG(Ae,Be) be the set of edges of G with one endvertex in Ae and one endvertex in Be. Letec(G:T)≔maxe |EG(Ae,Be)|.The paper is devoted to minimization of ec(G:T) • Over all trees with the same vertex set as G. • Over all spanning trees of G. These problems can be regarded as “congestion” problems.