Geodesic
Decompositions of a complete multidigraph into almost arbitrary paths
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 2, pp. 357-372.

Voir la notice de l'article provenant de la source Library of Science

For n ≥ 4, the complete n-vertex multidigraph with arc multiplicity λ is proved to have a decomposition into directed paths of arbitrarily prescribed lengths ≤ n - 1 and different from n - 2, unless n = 5, λ = 1, and all lengths are to be n - 1 = 4. For λ = 1, a more general decomposition exists; namely, up to five paths of length n - 2 can also be prescribed.
Keywords: complete digraph, multidigraph, tour girth, arbitrary path decomposition 
@article{DMGT_2012_32_2_a13,
     author = {Meszka, Mariusz and Skupie\'n, Zdzis{\l}aw},
     title = {Decompositions of a complete multidigraph into almost arbitrary paths},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {357--372},
     publisher = {mathdoc},
     volume = {32},
     number = {2},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_2_a13/}
}
TY  - JOUR
AU  - Meszka, Mariusz
AU  - Skupień, Zdzisław
TI  - Decompositions of a complete multidigraph into almost arbitrary paths
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 357
EP  - 372
VL  - 32
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_2_a13/
LA  - en
ID  - DMGT_2012_32_2_a13
ER  - 
%0 Journal Article
%A Meszka, Mariusz
%A Skupień, Zdzisław
%T Decompositions of a complete multidigraph into almost arbitrary paths
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 357-372
%V 32
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_2_a13/
%G en
%F DMGT_2012_32_2_a13
Meszka, Mariusz; Skupień, Zdzisław. Decompositions of a complete multidigraph into almost arbitrary paths. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 2, pp. 357-372. http://geodesic.mathdoc.fr/item/DMGT_2012_32_2_a13/

[1] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam-London, 1973).

[2] 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.

[3] J. Bosák, Decompositions of Graphs (Dordrecht, Kluwer, 1990).

[4] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman Hall/CRC Boca Raton, 2004).

[5] N.S. Mendelsohn, Hamiltonian decomposition of the complete directed n-graph, in: Theory of Graphs, Proc. Colloq., Tihany 1966, P. Erdös and G. Katona (Eds.), (Akadémiai Kiadó, Budapest, 1968) 237-241.

[6] 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.

[7] M. Meszka and Z. Skupień, Long paths decompositions of a complete digraph of odd order, Congr. Numer. 183 (2006) 203-211.

[8] M. Tarsi, Decomposition of a complete multigraph into simple paths: Nonbalanced handcuffed designs, J. Combin. Theory (A) 34 (1983) 60-70, doi: 10.1016/0097-3165(83)90040-7.

[9] T. Tillson, A Hamiltonian decomposition of $K*_{2m}$, 2m ≥ 8, J. Combin. Theory (B) 29 (1980) 68-74, doi: 10.1016/0095-8956(80)90044-1.