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 (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 18(2) (1998) 225-232
DOI: 10.7151/dmgt.1078

DECOMPOSITION OF MULTIGRAPHS

Mekkia Kouider
Maryvonne Mahéo

URA 410 L.R.I., Bât. 490, Universite Paris-Sud
91405 Orsay, France

Krzysztof Bryś
Zbigniew Lonc

Institute of Mathematics, Warsaw University of Technology
pl. Politechniki 1, 00-661 Warsaw, Poland

Abstract

In this note, we consider the problem of existence of an edge-decomposition of a multigraph into isomorphic copies of 2-edge paths K1,2. 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ń.

Keywords: edge decomposition, multigraph.

1991 Mathematics Subject Classification: Primary: 05C70, Secondary: 05C38.

References

[B] ] J.A. Bondy, Perfect Path Double Covers of Graphs, J. Graph Theory 14 (1990) 259-272, doi: 10.1002/jgt.3190140213.
[IMS] ] J. Ivančo, M. Meszka and Z. Skupień, Decomposition of multigraphs into isomorphic graphs with two edges, to appear in Ars Combinatoria.
[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.

Received 5 February 1998
Revised 28 July 1998