2024/02/21 by Ansong Ma, Ma, Ansong, Yuefang Sun +1
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2402.13786
openalex publication_date 2024/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study degree conditions for three types of disjoint directed path cover problems: many-to-many k-DDPC, one-to-many k-DDPC and one-to-one k-DDPC, which are intimately connected to other famous topics in graph theory, such as Hamiltonicity and k-linkage, and have a strong background of applications. Firstly, we get two sharp minimum semi-degree sufficient conditions for the unpaired many-to-many k-DDPC problem and a sharp Ore-type degree condition for the paired many-to-many 2-DDPC problem. Secondly, we obtain a minimum semi-degree sufficient condition for the one-to-many k-DDPC problem on a digraph with order n, and show that the bound for the minimum semi-degree is sharp when n+k is even and is sharp up to an additive constant 1 otherwise. Finally, we give a minimum semi-degree sufficient condition for the one-to-one k-DDPC problem on a digraph with order n, and show that the bound for the minimum semi-degree is sharp when n+k is odd and is sharp up to an additive constant 1 otherwise.