In this note, we consider the problem of existence of an edge-decomposition of a multigraph into isomorphic copies of 2-edge paths . We find necessary and sufficient conditions for such a decomposition of a multigraph H to exist when (i) either H does not have incident multiple edges or (ii) multiplicities of the edges in H are not greater than two. In particular, we answer a problem stated by Z. Skupień.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1078,
author = {Mekkia Kouider and Maryvonne Mah\'eo and Krzysztof Bry\'s and Zbigniew Lonc},
title = {Decomposition of multigraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {18},
year = {1998},
pages = {225-232},
zbl = {0926.05028},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1078}
}
Mekkia Kouider; Maryvonne Mahéo; Krzysztof Bryś; Zbigniew Lonc. Decomposition of multigraphs. Discussiones Mathematicae Graph Theory, Tome 18 (1998) pp. 225-232. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1078/
[000] [B] J.A. Bondy, Perfect Path Double Covers of Graphs, J. Graph Theory 14 (1990) 259-272, doi: 10.1002/jgt.3190140213. | Zbl 0745.05038
[001] [IMS] J. Ivančo, M. Meszka and Z. Skupień, Decomposition of multigraphs into isomorphic graphs with two edges, to appear in Ars Combinatoria. | Zbl 0977.05099
[002] [T] W.T. Tutte, The factorisation of linear graphs, J. London Math. Society 22 (1947) 107-111, doi: 10.1112/jlms/s1-22.2.107. | Zbl 0029.23301