ArticleOriginal scientific text

Title

Decompositions of multigraphs into parts with the same size

Authors 1

Affiliations

  1. Institute of Mathematics, P.J. Šafárik University, Jessenná 5, SK-041 54 Košice, Slovak Republic

Abstract

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 existence of such decompositions if ℱ consists of all multigraphs of size q except for one. Namely, for a multigraph H of size q we find each multigraph M of size kq, such that every partition of the edge set of M into parts of cardinality q contains a part which induces a submultigraph of M isomorphic to H.

Keywords

edge decompositions, multigraphs

Bibliography

  1. J. Ivanco, M. Meszka and Z. Skupień, Decompositions of multigraphs into parts with two edges, Discuss. Math. Graph Theory 22 (2002) 113-121, doi: 10.7151/dmgt.1162.
  2. W. Wang and K. Zhang, Equitable colorings of line graphs and complete r-partite graphs, Systems Science and Math. Sciences 13 (2000) 190-194.
Pages:
335-347
Main language of publication
English
Received
2008-12-31
Accepted
2009-09-30
Published
2010
Exact and natural sciences