PDF

Discussiones Mathematicae Graph Theory 32(2) (2012) 357-372
DOI: https://doi.org/10.7151/dmgt.1622

Decompositions of a Complete Multidigraph into Almost Arbitrary Paths

Mariusz Meszka and Zdzisław Skupień AGH University of Science and Technology Kraków, Poland

Abstract

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

2010 Mathematics Subject Classification: 05C20, 05C38, 05C45, 05C70.

References

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

Received 6 October 2010
Revised 4 November 2011
Accepted 14 November 2011