Decompositions of multigraphs into parts with the same size

• Autorzy: Jaroslav Ivanco
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

edge decompositions; multigraphs

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2010
• Tom: 30
• Numer: 2
• Strony: 335-347

Daty

wydano

2010

otrzymano

2008-12-31

poprawiono

2009-09-30

zaakceptowano

2009-11-09

Twórcy

autor

Jaroslav Ivanco

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1497