Geodesic
Decomposition of bipartite graphs into closed trails
Czechoslovak Mathematical Journal, Tome 59 (2009) no. 1, pp. 129-144 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let ${\rm 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 ${\rm 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\ge 1$ 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.
Let ${\rm 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 ${\rm 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\ge 1$ 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.
Classification : 05C38, 05C70
Keywords: even graph; closed trail; graph arbitrarily decomposable into closed trails; bipartite graph 
@article{CMJ_2009_59_1_a8,
     author = {Cichacz, Sylwia and Hor\v{n}\'ak, Mirko},
     title = {Decomposition of bipartite graphs into closed trails},
     journal = {Czechoslovak Mathematical Journal},
     pages = {129--144},
     year = {2009},
     volume = {59},
     number = {1},
     mrnumber = {2486620},
     zbl = {1224.05402},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2009_59_1_a8/}
}
TY  - JOUR
AU  - Cichacz, Sylwia
AU  - Horňák, Mirko
TI  - Decomposition of bipartite graphs into closed trails
JO  - Czechoslovak Mathematical Journal
PY  - 2009
SP  - 129
EP  - 144
VL  - 59
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_2009_59_1_a8/
LA  - en
ID  - CMJ_2009_59_1_a8
ER  - 
%0 Journal Article
%A Cichacz, Sylwia
%A Horňák, Mirko
%T Decomposition of bipartite graphs into closed trails
%J Czechoslovak Mathematical Journal
%D 2009
%P 129-144
%V 59
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_2009_59_1_a8/
%G en
%F CMJ_2009_59_1_a8
Cichacz, Sylwia; Horňák, Mirko. Decomposition of bipartite graphs into closed trails. Czechoslovak Mathematical Journal, Tome 59 (2009) no. 1, pp. 129-144. http://geodesic.mathdoc.fr/item/CMJ_2009_59_1_a8/