Decompositions of a complete multidigraph into almost arbitrary paths
Mariusz Meszka; Zdzisław Skupień
Discussiones Mathematicae Graph Theory (2012)
- Volume: 32, Issue: 2, page 357-372
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topMariusz Meszka, and Zdzisław Skupień. "Decompositions of a complete multidigraph into almost arbitrary paths." Discussiones Mathematicae Graph Theory 32.2 (2012): 357-372. <http://eudml.org/doc/270814>.
@article{MariuszMeszka2012,
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.},
author = {Mariusz Meszka, Zdzisław Skupień},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {complete digraph; multidigraph; tour girth; arbitrary path decomposition},
language = {eng},
number = {2},
pages = {357-372},
title = {Decompositions of a complete multidigraph into almost arbitrary paths},
url = {http://eudml.org/doc/270814},
volume = {32},
year = {2012},
}
TY - JOUR
AU - Mariusz Meszka
AU - Zdzisław Skupień
TI - Decompositions of a complete multidigraph into almost arbitrary paths
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 2
SP - 357
EP - 372
AB - 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.
LA - eng
KW - complete digraph; multidigraph; tour girth; arbitrary path decomposition
UR - http://eudml.org/doc/270814
ER -
References
top- [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. Zbl0344.05123
- [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). Zbl0890.05001
- [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. Zbl1084.05054
- [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. Zbl0511.05024
- [9] T. Tillson, A Hamiltonian decomposition of , 2m ≥ 8, J. Combin. Theory (B) 29 (1980) 68-74, doi: 10.1016/0095-8956(80)90044-1.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.