Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875609 | Theoretical Computer Science | 2018 | 9 Pages |
Abstract
A one-to-one k-disjoint directed path cover (k-DDPC for short) of a digraph D is a set of k disjoint directed paths joining source with sink that cover all the vertices of the digraph. Let δ0(D):=min{δ+(D),δâ(D)} be the minimum semi-degree of D. We show that every digraph D of sufficiently large order n with δ0(D)⩾â(n+k+1)/2â contains a one-to-one k-DDPC for any given one distinct source-sink. The undirected version and a Ore-type degree conditions of this result was proved earlier [1].
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Huabin Cao, Bicheng Zhang, Zhiheng Zhou,