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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1497,
author = {Jaroslav Ivanco},
title = {Decompositions of multigraphs into parts with the same size},
journal = {Discussiones Mathematicae Graph Theory},
volume = {30},
year = {2010},
pages = {335-347},
zbl = {1214.05124},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1497}
}
Jaroslav Ivanco. Decompositions of multigraphs into parts with the same size. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 335-347. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1497/
[000] [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. | Zbl 1018.05086
[001] [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. | Zbl 0979.05048