PDF
Discussiones Mathematicae Graph Theory 30(2) (2010)
335-347
DOI: https://doi.org/10.7151/dmgt.1497
DECOMPOSITIONS OF MULTIGRAPHS INTO PARTS WITH THE SAME SIZE
Jaroslav Ivanco
Institute of Mathematics
P.J. Safarik University, Jesenna 5
SK-041 54 Košice, Slovak Republic
e-mail: jaroslav.ivanco@upjs.sk
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 existence of such decompositions if F 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.
2010 Mathematics Subject Classification: 05C70.
References
| [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. |
Received 31 December 2008
Revised 30 September 2009
Accepted 9 November 2009
Close