Article ID Journal Published Year Pages File Type
6875609 Theoretical Computer Science 2018 9 Pages PDF
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].
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,