Subtrees of bipartite digraphs---the minimum degree condition (Q1962047): Difference between revisions

A digraph \(T\) without symmetric arcs is said to be an oriented tree if the graph obtained from \(T\) by replacing arcs by edges is a tree. Let \(\delta^+(D),\delta^-(D), \Delta^+(D)\) denote respectively the minimum outdegree, minimum indegree and maximum outdegree of \(D.\) The author shows that if \(\min\{\delta^+(D),\delta^-(D), \Delta^+(D)-1\}\geq k-2,\) then \(D\) contains every oriented tree with \(k\) vertices (Theorem 4). Let \(D\) be a bipartite digraph with \(V(D)=X\cup Y\) and \(X\cap Y=\varnothing.\) Two sharp conditions guaranteeing that \(D\) contains every oriented tree of order \(k\) are found: (1) \(\min\{\delta^+_X(D),\delta^-_Y(D)\}\geq k-1\) and \(\min\{\delta^-_X(D),\delta^+_Y(D)\}\geq\lfloor\frac{k-1}2\rfloor;\) (2) \(\min\{\delta^+_X(D),\delta^-_X(D)\}\geq k-1\) and \(\min\{\delta^+_Y(D),\delta^-_Y(D)\}\geq\lfloor\frac k2\rfloor.\)