An arc decomposition of the complete digraph Kₙ into t isomorphic subdigraphs is generalized to the case where the numerical divisibility condition is not satisfied. Two sets of nearly tth parts are constructively proved to be nonempty. These are the floor tth class ( Kₙ-R)/t and the ceiling tth class ( Kₙ+S)/t, where R and S comprise (possibly copies of) arcs whose number is the smallest possible. The existence of cyclically 1-generated decompositions of Kₙ into cycles and into paths is characterized.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1464,
author = {Mariusz Meszka and Zdzis\l aw Skupie\'n},
title = {Decompositions of nearly complete digraphs into t isomorphic parts},
journal = {Discussiones Mathematicae Graph Theory},
volume = {29},
year = {2009},
pages = {563-572},
zbl = {1193.05132},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1464}
}
Mariusz Meszka; Zdzisław Skupień. Decompositions of nearly complete digraphs into t isomorphic parts. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 563-572. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1464/
[000] [1] B. Alspach, H. Gavlas, M. Sajna and H. Verrall, Cycle decopositions IV: complete directed graphs and fixed length directed cycles, J. Combin. Theory (A) 103 (2003) 165-208, doi: 10.1016/S0097-3165(03)00098-0. | Zbl 1022.05061
[001] [2] C. Berge, Graphs and Hypergraphs (North-Holland, 1973).
[002] [3] J.C. Bermond and V. Faber, Decomposition of the complete directed graph into k-circuits, J. Combin. Theory (B) 21 (1976) 146-155, doi: 10.1016/0095-8956(76)90055-1. | Zbl 0344.05123
[003] [4] J. Bosák, Decompositions of Graphs (Dordrecht, Kluwer, 1990, [Slovak:] Bratislava, Veda, 1986).
[004] [5] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman & Hall, 1996). | Zbl 0890.05001
[005] [6] A. Fortuna and Z. Skupień, On nearly third parts of complete digraphs and complete 2-graphs, manuscript. | Zbl 1276.05077
[006] [7] F. Harary and R.W. Robinson, Isomorphic factorizations X: Unsolved problems, J. Graph Theory 9 (1985) 67-86, doi: 10.1002/jgt.3190090105. | Zbl 0617.05051
[007] [8] F. Harary, R.W. Robinson and N.C. Wormald, Isomorphic factorisation V: Directed graphs, Mathematika 25 (1978) 279-285, doi: 10.1112/S0025579300009529. | Zbl 0387.05015
[008] [9] A. Kedzior and Z. Skupień, Universal sixth parts of a complete graph exist, manuscript.
[009] [10] E. Lucas, Récréations Mathématiques, vol. II (Paris, Gauthier-Villars, 1883).
[010] [11] M. Meszka and Z. Skupień, Self-converse and oriented graphs among the third parts of nearly complete digraphs, Combinatorica 18 (1998) 413-424, doi: 10.1007/PL00009830. | Zbl 0924.05052
[011] [12] M. Meszka and Z. Skupień, On some third parts of nearly complete digraphs, Discrete Math. 212 (2000) 129-139, doi: 10.1016/S0012-365X(99)00214-9. | Zbl 0940.05054
[012] [13] M. Meszka and Z. Skupień, Decompositions of a complete multidigraph into nonhamiltonian paths, J. Graph Theory 51 (2006) 82-91, doi: 10.1002/jgt.20122. | Zbl 1084.05054
[013] [14] M. Plantholt, The chromatic index of graphs with a spanning star, J. Graph Theory 5 (1981) 45-53, doi: 10.1002/jgt.3190050103. | Zbl 0448.05031
[014] [15] R.C. Read, On the number of self-complementary graphs and digraphs, J. London Math. Soc. 38 (1963) 99-104, doi: 10.1112/jlms/s1-38.1.99. | Zbl 0116.15001
[015] [16] Z. Skupień, The complete graph t-packings and t-coverings, Graphs Combin. 9 (1993) 353-363, doi: 10.1007/BF02988322. | Zbl 0795.05116
[016] [17] Z. Skupień, Clique parts independent of remainders, Discuss. Math. Graph Theory 22 (2002) 361, doi: 10.7151/dmgt.1181. | Zbl 1028.05077
[017] [18] Z. Skupień, Universal fractional parts of a complete graph, manuscript.