| Title:
|
Decomposition of bipartite graphs into closed trails (English) |
| Author:
|
Cichacz, Sylwia |
| Author:
|
Horňák, Mirko |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
59 |
| Issue:
|
1 |
| Year:
|
2009 |
| Pages:
|
129-144 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
even graph |
| Keyword:
|
closed trail |
| Keyword:
|
graph arbitrarily decomposable into closed trails |
| Keyword:
|
bipartite graph |
| MSC:
|
05C38 |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 1224.05402 |
| idMR:
|
MR2486620 |
| . |
| Date available:
|
2010-07-20T14:55:50Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140468 |
| . |
| Reference:
|
[1] Balister, P. N.: Packing circuits into $K_N$.Comb. Probab. Comput. 6 (2001), 463-499. Zbl 1113.05309, MR 1869841, 10.1017/S0963548301004771 |
| Reference:
|
[2] Balister, P. N.: Packing closed trails into dense graphs.J. Comb. Theory, Ser. B 88 (2003), 107-118. Zbl 1045.05074, MR 1973263, 10.1016/S0095-8956(02)00039-4 |
| Reference:
|
[3] Balister, P. N.: Packing digraphs with directed closed trails.Comb. Probab. Comput. 12 (2003), 1-15. Zbl 1015.05072, MR 1967482, 10.1017/S0963548302005461 |
| Reference:
|
[4] Chou, Ch.-Ch., Fu, Ch.-M., Huang, W.-Ch.: Decomposition of $K_{n,m}$ into short cycle.Discrete Math. 197/198 (1999), 195-203. MR 1674862 |
| Reference:
|
[5] Cichacz, S.: Decomposition of complete bipartite digraphs and even complete bipartite multigraphs into closed trails.Discuss. Math. Graph Theory 27 (2007), 241-249. Zbl 1133.05075, MR 2355718, 10.7151/dmgt.1358 |
| Reference:
|
[6] Cichacz, S., Przybyło, J., Wo'zniak, M.: Decompositions of pseudographs into closed trails of even sizes.Discrete Math., doi:10.1016/j.disc.2008.04.024. 10.1016/j.disc.2008.04.024 |
| Reference:
|
[7] Horňák, M., Kocková, Z.: On complete tripartite graphs arbitrarily decomposable into closed trails.Tatra Mt. Math. Publ. 36 (2007), 71-107. MR 2378742 |
| Reference:
|
[8] Horňák, M., Wo'zniak, M.: Decomposition of complete bipartite even graphs into closed trails.Czech. Math. J. 53 (2003), 127-134. MR 1962004, 10.1023/A:1022931710349 |
| . |
