Partition of a Subset into Two Directed Cycles with Partial Degrees
Pith reviewed 2026-05-24 15:19 UTC · model grok-4.3
The pith
In a directed graph of order n at least 6, if every vertex in a subset W of size at least 6 has degree at least (3n-3)/2, then W admits any bipartition into sizes n1 and n2 both at least 3 realized by the intersections with two vertex-disjO
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Let D be a directed graph of order n at least 6. Let W be a subset of V(D) with |W| at least 6. If every vertex of W has degree at least (3n-3)/2 in D, then for every pair of integers n1 and n2 with n1 at least 3, n2 at least 3 and n1 plus n2 equal to |W|, there exist two vertex-disjoint directed cycles C1 and C2 in D such that the number of vertices of C1 that belong to W is exactly n1 and the number of vertices of C2 that belong to W is exactly n2.
What carries the argument
The minimum degree threshold (3n-3)/2 imposed on all vertices of W, which is used to guarantee the existence of the two disjoint directed cycles whose intersections with W match any admissible size partition.
If this is right
- The two cycles exist simultaneously for every admissible choice of n1 and n2.
- The same degree lower bound is necessary in the sense that dropping it by one permits counterexamples for some partitions.
- The conclusion applies uniformly to every digraph satisfying the stated numerical hypothesis on W.
- An analogous statement with k at least 3 cycles covering a k-partition of W is conjectured to hold under identical degree assumptions.
Where Pith is reading between the lines
- If the k-cycle conjecture is true, the result would supply a flexible cycle-factor theorem for subsets of vertices under a single uniform degree bound.
- The threshold (3n-3)/2 may be compared with classical degree conditions that guarantee a single directed Hamilton cycle through all of W.
- Sharpness examples for the two-cycle case could be adapted to test the minimal degree needed when k exceeds 2.
Load-bearing premise
The combined in-degree and out-degree of each vertex inside W is at least (3n-3)/2.
What would settle it
A directed graph on n vertices together with a subset W in which every vertex has degree exactly (3n-4)/2 yet, for some n1 and n2 at least 3 summing to |W|, no pair of vertex-disjoint directed cycles meets W in exactly those cardinalities.
read the original abstract
Let $D=(V,A)$ be a directed graph of order $n\geq 6$. Let $W$ be a subset of $V$ with $|W|\geq 6$. Suppose that every vertex of $W$ has degree at least $(3n-3)/2$ in $D$. Then for any integer partition $|W|=n_1+n_2$ with $n_1\geq 3$ and $n_2\geq 3$, $D$ contains two disjoint directed cycles $C_1$ and $C_2$ such that $|V(C_1)\cap W|=n_1$ and $|V(C_2)\cap W|=n_2$. We conjecture that for any integer partition $|W|=n_1+n_2+\cdots +n_k$ with $k\geq 3$ and $n_i\geq 3(1\leq i\leq k)$, $D$ contains $k$ disjoint directed cycles $C_1,C_2,\ldots , C_k$ such that $|V(C_i)\cap W|=n_i$ for all $1\leq i\leq k$. The degree condition is sharp in general.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims that for a directed graph D of order n≥6 and a subset W⊆V with |W|≥6, if every vertex in W has degree at least (3n−3)/2, then for any partition |W|=n1+n2 with n1,n2≥3 there exist two vertex-disjoint directed cycles C1,C2 such that |V(C1)∩W|=n1 and |V(C2)∩W|=n2. It further conjectures the analogous statement for k≥3 cycles and asserts that the given degree bound is sharp in general.
Significance. If correct, the result supplies a sharp degree condition guaranteeing a partition of a prescribed subset into two directed cycles of given intersection sizes. This would constitute a concrete advance in the area of degree conditions for directed cycle factors and partitions, with the explicit sharpness statement adding value by delineating the boundary of the theorem.
major comments (1)
- [Abstract] The provided abstract states the main theorem but contains no proof, outline, or reference to a derivation. This creates a load-bearing gap: without the argument it is impossible to confirm that the numerical threshold (3n−3)/2 actually suffices for the stated cycle partition.
Simulated Author's Rebuttal
We thank the referee for their report. The major comment concerns the abstract's lack of a proof outline. We respond point-by-point below.
read point-by-point responses
-
Referee: [Abstract] The provided abstract states the main theorem but contains no proof, outline, or reference to a derivation. This creates a load-bearing gap: without the argument it is impossible to confirm that the numerical threshold (3n−3)/2 actually suffices for the stated cycle partition.
Authors: Abstracts in research papers in mathematics are expected to state the main theorem concisely without proofs or derivations; the full argument appears in the body of the manuscript. The proof that the degree bound (3n−3)/2 suffices, including all details on the existence of the two vertex-disjoint directed cycles realizing the partition of W, is developed in the sections following the abstract. The referee is referred to that argument for verification. revision: no
Circularity Check
No significant circularity
full rationale
The paper states a standard combinatorial existence theorem: under an explicit minimum degree condition on subset W, any bipartition of |W| is realized by the intersections of two vertex-disjoint directed cycles. No equations, fitted parameters, or self-referential definitions appear; the degree threshold is asserted to be sharp but is not derived from the conclusion. The k-cycle extension is labeled a conjecture and plays no role in the two-cycle claim. The derivation is therefore self-contained against external graph-theoretic benchmarks and receives score 0.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard definitions and basic properties of directed graphs, degrees, and cycles from graph theory.
Reference graph
Works this paper leans on
-
[1]
M. Aigner and S. Brandt, Embedding arbitrary graphs of maximum degree two, J. Lon- don Math. Soc. , (2) 48 (1993), 39–51
work page 1993
-
[2]
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications , The Macmillan Press, London, 1976
work page 1976
-
[3]
K. Corr´ adi and A. Hajnal, On the maximal number of independen t circuits in a graph, Acta Math. Acad. Sci. Hungar . 14(1963), 423–439
work page 1963
-
[4]
Dirac, Some theorems on abstract graphs, Proc
G. Dirac, Some theorems on abstract graphs, Proc. London. Math. 21(1972), 111–113
work page 1972
-
[5]
El-Zahar, On circuits in graphs, Discrete Math
M.H. El-Zahar, On circuits in graphs, Discrete Math. 50(1984), 227–230
work page 1984
-
[6]
P. Erd˝ os and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10(1959), 337–356
work page 1959
-
[7]
C. Little and H. Wang, Vertex-disjoint cycles in a directed graph, The Australasian Journal of Combinatorics , 12(1995), 113-119
work page 1995
-
[8]
N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory B , 25(1978), 295–302
work page 1978
-
[9]
Ronghua Shi, 2-neighborhoods and hamiltonian conditions, Journal of Graph Theory , (3) 16(1992), 267–271
work page 1992
-
[10]
H. Wang, Proof of the Erd˝ os-Faudree Conjecture on Quadr ilaterals, Graphs and Com- binatorics, 26(2010), 833-877
work page 2010
-
[11]
H. Wang, Digraphs Containing Every Possible Pair of Dicycles, Journal of Graph The- ory, 34(2000), 154–162
work page 2000
-
[12]
H. Wang, Independent directed triangles in a directed graph, Graphs and Combinatorics, 16(2000), 453–462
work page 2000
-
[13]
Wang, Partial Degree Conditions and Cycle Coverings, Journal of Graph Theory , 78(2015), 295-304
H. Wang, Partial Degree Conditions and Cycle Coverings, Journal of Graph Theory , 78(2015), 295-304
work page 2015
-
[14]
H. Wang, Covering a subset with two cycles, Australasian Journal of Combinatorics , Volume 65(1) (2016), Pages 27-36
work page 2016
-
[15]
Wang, Directed Cycles in a Digraphs with Partial Degrees, man uscript
H. Wang, Directed Cycles in a Digraphs with Partial Degrees, man uscript. 12
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.