Some generalizations of Menger's theorem concerning arc-connected digraphs
This short paper gives two necessary and sufficient conditions for a digraph to be \(k\)-arc-connected: (1) Let \(D\) be a digraph with at least \(k\) arcs. Then \(D\) is \(k\)-arc-connected if and only if for any \(k\) distinct arcs \(f_i= x_iy_i\), \(i=1,2,\dots, k\), \(D-\{f_1, f_2,\dots, f_k\}\) contains \(k\) arc-disjoint spanning arborescences \(T_1,\dots, T_k\) such that \(T_i\) is rooted at \(y_i\) for each \(i\). (2) Let \(D\) be a \(k\)-arc-connected digraph. Then, for any \(k\) triples \((x_1,f_1,y_1),\dots, (x_k, f_k, y_k)\), where \(x_1,\dots, x_k\), \(y_1,\dots, y_k\) are from \(V(D)\), but not necessarily distinct, and \(f_1,\dots, f_k\) are distinct arcs with \(f_i\in E^+(x_i)\), \(i=1,\dots, k\) (resp. \(f_i\in E^-(y_i)\), \(i=1,\dots, k\)) there exist \(k\) arc-disjoint \(x_i\)-\(y_i\) paths \(P_i\) in \(D\) such that \(f_i\in E(P_i)\), \(i= 1,\dots, k\).
This page was built for publication: Some generalizations of Menger's theorem concerning arc-connected digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377773)
