2022/08/19 by Ansong Ma, Ma, Ansong, Yuefang Sun +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2208.09313
openalex publication_date 2022/08/19 · openalex created_date 2022/08/23 · openalex updated_date 2026/07/28
Let D be a digraph. We define the minimum semi-degree of D as δ0(D) := min \δ+(D), δ-(D)\. Let k be a positive integer, and let S = \s\ and T = \t1, … ,tk\ be any two disjoint subsets of V(D). A set of k internally disjoint paths joining source set S and sink set T that cover all vertices D are called a one-to-many k-disjoint directed path cover (k-DDPC for short) of D. A digraph D is semicomplete if for every pair x,y of vertices of it, there is at least one arc between x and y. In this paper, we prove that every semicomplete digraph D of sufficiently large order n with δ0(D) ≥ \lceil (n+k-1)/2\rceil has a one-to-many k-DDPC joining any disjoint source set S and sink set T, where S = \s\, T = \t1, …, tk\.