Subtrees of bipartite digraphs---the minimum degree condition
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.\)
- Degree sum conditions for oriented forests in digraphs
- Spanning trees in dense directed graphs
- Oriented Forests in Directed Graphs
- Subforests of bipartite digraphs---the minimum degree condition
- scientific article; zbMATH DE number 7771746 (Why is no real title available?)
- Counting oriented trees in digraphs with large minimum semidegree
- Spanning trees: A survey
This page was built for publication: Subtrees of bipartite digraphs---the minimum degree condition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962047)
