Abstract
In this paper, we extend the study of C4-decompositions of the complete graph with 2-regular leaves and paddings to directed versions. Mainly, we prove that if P is a vertex-disjoint union of directed cycles in a complete digraph D
v
, then and D
v
∪P can be decomposed into directed 4-cycles, respectively, if and only if v(v−1)−|E(P)|≡0(mod 4) and v(v−1)+|E(P)|≡0(mod 4) where |E(P)| denotes the number of directed edges of P, and v≥8.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Colbourn, C. J., Rosa, A.: Quadratic excess of coverings by triples, Ars. Combin. 2, 23–30 (1987)
Fu, C. M., Fu, H. L., Rodger C. A., Smith, T.: All graphs with maximum degree three whose complements have 4-cycle decompositions, Discrete Math., to appear.
Fu, C. M., Fu H. L., Rodger, C. A.: Decomposing K n ∪P into triangles, Discrete Math. 284, 131–136 (2004)
Fu, H. L., Rodger, C. A.: Four-cycle systems with two regular leaves, Graphs and Combinatorics, 17, 457–461 (2001)
Schönheim, J.: Partition of the edges of the complete directed graph into 4-cycles. Discrete Math. 11, 67–70 (1975)
Schönheim, J., Bialostocki, A.: Packing and covering the complete graph with 4-cycles, Canadian Math. Bullitin 18, 703–708 (1975)
Sotteau, D.: Decomposition of Km,n (Km,n*) into cycles (circuits) of length 2k, J. Combinatorial Theorem (Series B) 30, 75–81
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pu, L., Fu, HL. & Shen, H. -Decompositions of
and D
v
∪P where P is a 2-Regular Subgraph of D
v
.
Graphs and Combinatorics 22, 515–525 (2006). https://doi.org/10.1007/s00373-006-0683-y
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s00373-006-0683-y