Czechoslovak Mathematical Journal, Vol. 59, No. 1, pp. 129-144, 2009

Decomposition of bipartite graphs into closed trails

Sylwia Cichacz, Mirko Hornak

Sylwia Cichacz, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krakow, Poland, e-mail:; Mirko Hornak, P. J. Safarik University, Jesenna 5, 040 01 Kosice, Slovakia, e-mail:

Abstract: Let ${\Lct}(G)$ denote the set of all lengths of closed trails that exist in an even graph $G$. A sequence $(t_1,\dots,t_p)$ of elements of ${\Lct}(G)$ adding up to $|E(G)|$ is $G$-realisable provided there is a sequence $(T_1,\dots,T_p)$ of pairwise edge-disjoint closed trails in $G$ such that $T_i$ is of length $t_i$ for $i=1,\dots,p$. The graph $G$ is arbitrarily decomposable into closed trails if all possible sequences are $G$-realisable. In the paper it is proved that if $a\ge1$ is an odd integer and $M_{a,a}$ is a perfect matching in $K_{a,a}$, then the graph $K_{a,a}-M_{a,a}$ is arbitrarily decomposable into closed trails.

Keywords: even graph, closed trail, graph arbitrarily decomposable into closed trails, bipartite graph

Classification (MSC 2000): 05C70

Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at
Subscribers of Springer need to access the articles on their site, which is

[Previous Article] [Next Article] [Contents of This Number] [Contents of Czechoslovak Mathematical Journal]