Decompositions of multigraphs into parts with two edges
Jaroslav Ivančo ; Mariusz Meszka ; Zdzisław Skupień
Discussiones Mathematicae Graph Theory, Tome 22 (2002), p. 113-121 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Given a family 𝓕 of multigraphs without isolated vertices, a multigraph M is called 𝓕-decomposable if M is an edge disjoint union of multigraphs each of which is isomorphic to a member of 𝓕. We present necessary and sufficient conditions for the existence of such decompositions if 𝓕 comprises two multigraphs from the set consisting of a 2-cycle, a 2-matching and a path with two edges.

Publié le : 2002-01-01
EUDML-ID : urn:eudml:doc:270217 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1162,
     author = {Jaroslav Ivan\v co and Mariusz Meszka and Zdzis\l aw Skupie\'n},
     title = {Decompositions of multigraphs into parts with two edges},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {22},
     year = {2002},
     pages = {113-121},
     zbl = {1018.05086},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1162}
}

Jaroslav Ivančo; Mariusz Meszka; Zdzisław Skupień. Decompositions of multigraphs into parts with two edges. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 113-121. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1162/

[000] [1] K. Bryś, M. Kouider, Z. Lonc and M. Mahéo, Decomposition of multigraphs, Discuss. Math. Graph Theory 18 (1998) 225-232, doi: 10.7151/dmgt.1078. | Zbl 0926.05028

[001] [2] Y. Caro, The decomposition of graphs into graphs having two edges, a manuscript.

[002] [3] Y. Caro and J. Schönheim, Decompositions of trees into isomorphic subtrees, Ars Comb. 9 (1980) 119-130. | Zbl 0454.05022

[003] [4] J. Ivančo, M. Meszka and Z. Skupień; Decomposition of multigraphs into isomorphic graphs with two edges, Ars Comb. 51 (1999) 105-112.

[004] [5] E.B. Yavorski, Representations of oriented graphs and φ-transformations [Russian], in: A. N. Sarkovski, ed., Theoretical and Applied Problems of Differential Equations and Algebra [Russian] (Nauk. Dumka, Kiev, 1978) 247-250.

[005] [6] M. Las Vergnas, A note on matchings in graphs, Cahiers Centre Etudes Rech. Opér. 17 (1975) 257-260.

[006] [7] Z. Skupień; Problem 270 [on 2-edge-decomposable multigraphs], Discrete Math. 164 (1997) 320-321.

[007] [8] D.P. Sumner, Graphs with 1-factors, Proc. Amer. Math. Soc. 42 (1974) 8-12. | Zbl 0293.05157