Decomposition of multigraphs

• Autorzy: Mekkia Kouider , Maryvonne Mahéo , Krzysztof Bryś , Zbigniew Lonc
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

edge decomposition; multigraph

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1998
• Tom: 18
• Numer: 2
• Strony: 225-232

Daty

wydano

1998

otrzymano

1998-02-05

poprawiono

1998-07-28

Twórcy

autor

Mekkia Kouider

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

autor

Maryvonne Mahéo

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

autor

Krzysztof Bryś

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

autor

Zbigniew Lonc

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

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1078