DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 22(1) (2002) 113-121
DOI: 10.7151/dmgt.1162

DECOMPOSITIONS OF MULTIGRAPHS INTO PARTS WITH TWO EDGES

 Jaroslav Ivanco

Department of Geometry and Algebra
Saf࠲ik University
Jesennߠ5, 041 54 Košice, Slovakia
e-mail: ivanco@duro.upjs.sk

Mariusz Meszka and Zdzisław Skupień

Faculty of Applied Mathematics AGH
University of Mining and Metallurgy
al. Mickiewicza 30, 30-059 Krakಷ, Poland
e-mail: grmeszka@cyf-kr.edu.pl
e-mail: skupien@uci.agh.edu.pl

Abstract

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

 Keywords: edge decomposition, multigraph, line graph, 1-factor.

 2000 Mathematics Subject Classification: 05C70.

References

[1] K. Bryś, M. Kouider, Z. Lonc and M. Mahਯ, Decomposition of multigraphs, Discuss. Math. Graph Theory 18 (1998) 225-232, doi: 10.7151/dmgt.1078.
[2] Y. Caro, The decomposition of graphs into graphs having two edges, a manuscript.
[3] Y. Caro and J. Sch൮heim, Decompositions of trees into isomorphic subtrees, Ars Comb. 9 (1980) 119-130.
[4] J. Ivanco, M. Meszka and Z. Skupie௬ Decomposition of multigraphs into isomorphic graphs with two edges, Ars Comb. 51 (1999) 105-112.
[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.
[6] M. Las Vergnas, A note on matchings in graphs, Cahiers Centre Etudes Rech. Opਲ. 17 (1975) 257-260.
[7] Z. Skupie௬ Problem 270 [on 2-edge-decomposable multigraphs], Discrete Math. 164 (1997) 320-321.
[8] D.P. Sumner, Graphs with 1-factors, Proc. Amer. Math. Soc. 42 (1974) 8-12.

Received 4 October 2000
Revised 28 May 2001