Subtrees of bipartite digraphs---the minimum degree condition (Q1962047): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Matúš Harminc / rank | |||
Property / reviewed by | |||
Property / reviewed by: Matúš Harminc / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cycles and paths of many lengths in bipartite digraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Longest paths in digraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Subtrees and subforests of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Long paths and cycles in oriented graphs / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0166-218x(99)00137-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1968218710 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:57, 30 July 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