Edge-disjoint trees containing some given vertices in a graph (Q1405100): Difference between revisions

The graphs \(G\) considered are finite and may contain multiple edges. The edge-connectivity \(\lambda (x,y;G)\) of distinct vertices \(x,y\) of \(G\) is the largest number \(\lambda \) such that there is a system of \(\lambda \) edge-disjoint \(x,y\) paths in \(G\). A set \(A\) of vertices of \(G\) is \(n\)-edge-connected if \(\lambda (x,y;G)\geq n\) for all \(x\neq y\) in \(A.\) A subtree \(T\) of \(G\) is called an \(A\)-spanning tree if \(A\) is contained in the vertices of \(T\). An aim of this work is to show there exists a natural number \(f_h(k)\) (\(g_h(k))\) such that for every \(f_h(k)\)-edge-connected (\(g_h(k)\)-edge connected) vertex set \(A\) of \(G\) with \(|A|\leq h\) (\(|V(G)-A|\leq h\)), there exists a system of \(k\) edge-disjoint \(A\)-spanning trees. Conjecture 1 says \(f_h(k)\leq 2k.\) It is shown that \(f_3(k)=\left\lfloor \frac{8k+3}6\right\rfloor .\) And the smallest numbers \(f_h^{*}(k)\) are determined such that every \(f_h^{*}(k)\)-edge connected graph on at most \(h\) vertices contains a system of \(k\) edge-disjoint spanning trees. Applications to line graphs are given.