ArticleOriginal scientific text

Title

Decomposition of multigraphs

Authors 1, 1, 2, 2

Affiliations

  1. URA 410 L.R.I., Bât. 490, Universite Paris-Sud, 91405 Orsay, France
  2. 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

Bibliography

  1. [B] J.A. Bondy, Perfect Path Double Covers of Graphs, J. Graph Theory 14 (1990) 259-272, doi: 10.1002/jgt.3190140213.
  2. [IMS] J. Ivančo, M. Meszka and Z. Skupień, Decomposition of multigraphs into isomorphic graphs with two edges, to appear in Ars Combinatoria.
  3. [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.
Pages:
225-232
Main language of publication
English
Received
1998-02-05
Accepted
1998-07-28
Published
1998
Exact and natural sciences