کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656672 1632973 2016 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Disjoint dijoins
ترجمه فارسی عنوان
دی جیین جدا نیست
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A “dijoin” in a digraph is a set of edges meeting every directed cut. D.R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then there are k pairwise disjoint dijoins. This remains open, but a capacitated version is known to be false. In particular, A. Schrijver gave a digraph G and a subset S of its edge-set, such that every directed cut contains at least two edges in S, and yet there do not exist two disjoint dijoins included in S. In Schrijver's example, G is planar, and the subdigraph formed by the edges in S consists of three disjoint paths.We conjecture that when k=2k=2, the disconnectedness of S is crucial: more precisely, that if G   is a digraph, and S⊆E(G)S⊆E(G) forms a connected subdigraph (as an undirected graph), and every directed cut of G contains at least two edges in S, then we can partition S into two dijoins.We prove this in two special cases: when G is planar, and when the subdigraph formed by the edges in S is a subdivision of a caterpillar.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 120, September 2016, Pages 18–35
نویسندگان
, , , , ,