Sylwia Cichacz, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krakow, Poland, e-mail: cichacz@agh.edu.pl; Mirko Hornak, P. J. Safarik University, Jesenna 5, 040 01 Kosice, Slovakia, e-mail: mirko.hornak@upjs.sk
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 myris@myris.cz.
Subscribers of Springer need to access the articles on their site, which is http://www.springeronline.com/10587.