Subtrees of bipartite digraphs---the minimum degree condition (Q1962047): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 17:36, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Subtrees of bipartite digraphs---the minimum degree condition |
scientific article |
Statements
Subtrees of bipartite digraphs---the minimum degree condition (English)
0 references
20 March 2000
0 references
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.\)
0 references
oriented tree
0 references
bipartite digraph
0 references