Decomposition of oriented k-partition-connected digraphs

From Egres Open
Jump to: navigation, search

Let D=(V,A) be a digraph whose underlying graph is k-partition-connected, and let r0V be a node of in-degree 0. Suppose that the in-degree of every other node is at least k. Is it true that D can be decomposed into k weakly connected spanning subgraphs, so that every node vVr0 has positive in-degree in each subgraph?


Remarks

Let M1 be the cycle matroid of the underlying undirected graph of D, and let M2 be the partition matroid where each class consists of the set of edges entering a given node vVr0. The problem can be formulated as follows:

Is it true that if both M1 and M2 contain k disjoint spanning sets, then there are k disjoint common spanning sets?

This statement is known to be true for strongly base orderable matroids [1]; however, the cycle matroid of a graph is not necessarily base orderable.

References

  1. J. Davies, C. McDiarmid, Disjoint common transversals and exchange structures, Journal of the London Mathematical Society s2-14 (1976), 55-62. DOI link.