2020/01/31 by Yun Wang, Jin Yan, Wang, Yun +1
Computer Science · Engineering · Mathematics · #05C20 #05C38 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2001.11703
openalex publication_date 2020/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let D=(V,A) be a digraph of order n and let W be any subset of V. We define the minimum semi-degree of W in D to be δ0(W)=min\δ+(W),δ-(W)\, where δ+(W) is the minimum out-degree of W in D and δ-(W) is the minimum in-degree of W in D. Let k be an integer with k≥ 1. In this paper, we prove that for any positive integer partition |W|=∑i=1kni with ni≥ 2 for each i, if δ0(W)≥ (3n-3)/(4), then there are k vertex disjoint cycles C1,…,Ck in D such that each Ci contains exactly ni vertices of W. Moreover, the lower bound of δ0(W) can be improved to (n)/(2) if k=1, and (n)/(2)+|W|-1 if n≥ 2|W|. The minimum semi-degree condition δ0(W)≥ (3n-3)/(4) is sharp in some sense and this result partially confirms the conjecture posed by Wang [Graphs and Combinatorics 16 (2000) 453-462]. It is also a directed version of the Sauer-Spender Theorem on vertex disjoint cycles in graphs [J. Combin. Theory B, 25 (1978) 295-302].