Decomposition of complete bipartite digraphs and even complete bipartite multigraphs into closed trails

• Autorzy: Sylwia Cichacz
• Języki publikacji: EN

Abstrakty

EN

It has been shown [3] that any bipartite graph $K_{a,b}$, where a, b are even integers, can be decomposed into closed trails with prescribed even lengths. In this article, we consider the corresponding question for directed bipartite graphs. We show that a complete directed bipartite graph $^↔ K_{a,b}$ is decomposable into directed closed trails of even lengths greater than 2, whenever these lengths sum up to the size of the digraph. We use this result to prove that complete bipartite multigraphs can be decomposed in a similar manner.

Słowa kluczowe

EN

trail; decomposition

Kategorie tematyczne

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2007
• Tom: 27
• Numer: 2
• Strony: 241-249

Daty

wydano

2007

otrzymano

2005-12-13

poprawiono

2007-01-25

zaakceptowano

2007-04-10

Twórcy

autor

Sylwia Cichacz

• AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Kraków, Poland

Bibliografia

• [1] P.N. Balister, Packing Circuits into Kₙ, Combin. Probab. Comput. 10 (2001) 463-499, doi: 10.1017/S0963548301004771.
• [2] P.N. Balister, Packing digraphs with directed closed trails, Combin. Probab. Comput. 12 (2003) 1-15, doi: 10.1017/S0963548302005461.
• [3] M. Hornák and M. Woźniak, Decomposition of complete bipartite even graphs into closed trails, Czechoslovak Math. J. 128 (2003) 127-134.

Identyfikatory

DOI

10.7151/dmgt.1358