| Title:
|
Decomposing complete tripartite graphs into closed trails of arbitrary lengths (English) |
| Author:
|
Billington, Elizabeth J. |
| Author:
|
Cavenagh, Nicholas J. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
57 |
| Issue:
|
2 |
| Year:
|
2007 |
| Pages:
|
523-551 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
The complete tripartite graph $K_{n,n,n}$ has $3n^2$ edges. For any collection of positive integers $x_1,x_2,\dots ,x_m$ with $\sum _{i=1}^m x_i=3n^2$ and $x_i\ge 3$ for $1\le i\le m$, we exhibit an edge-disjoint decomposition of $K_{n,n,n}$ into closed trails (circuits) of lengths $x_1,x_2,\dots ,x_m$. (English) |
| Keyword:
|
cycles |
| Keyword:
|
decomposing complete tripartite graphs |
| MSC:
|
05C38 |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 1174.05100 |
| idMR:
|
MR2337613 |
| . |
| Date available:
|
2009-09-24T11:47:26Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128188 |
| . |
| Reference:
|
[1] P. Balister: Packing circuits into $K_N$.Combinatorics, Probability and Computing 10 (2001), 463–499. Zbl 1113.05309, MR 1869841, 10.1017/S0963548301004771 |
| Reference:
|
[2] P. Balister: Packing closed trails into dense graphs.J. Combinatorial Theory, Ser. B 88 (2003), 107–118. Zbl 1045.05074, MR 1973263, 10.1016/S0095-8956(02)00039-4 |
| Reference:
|
[3] E. J. Billington: Decomposing complete tripartite graphs into cycles of length $3$ and $4$.Discrete Math. 197/198 (1999), 123–135. MR 1674855 |
| Reference:
|
[4] E. J. Billington: Combinatorial trades: a survey of recent results.Chapter 3 in Designs 2002: Further Computational and Constructive Design Theory (ed. W. D. Wallis), Kluwer Academic Publishers, Boston/Dordrecht/London, 2003, pp. 47–67. Zbl 1056.05014, MR 2041871 |
| Reference:
|
[5] N. J. Cavenagh: Decompositions of complete tripartite graphs into $k$-cycles.Australas. J. Combin. 18 (1998), 193–200. Zbl 0924.05051, MR 1658341 |
| Reference:
|
[6] N. J. Cavenagh: Further decompositions of complete tripartite graphs into $5$-cycles.Discrete Math. 256 (2002), 55–81. Zbl 1009.05108, MR 1927056 |
| Reference:
|
[7] N. J. Cavenagh and E. J. Billington: On decomposing complete tripartite graphs into $5$-cycles.Australas. J. Combin. 22 (2000), 41–62. MR 1795321 |
| Reference:
|
[8] N. J. Cavenagh and E. J. Billington: Decompositions of complete multipartite graphs into cycles of even length.Graphs and Combinatorics 16 (2000), 49–65. MR 1750460, 10.1007/s003730050003 |
| Reference:
|
[9] M. Horňák and M. Woźniak: Decomposition of complete bipartite even graphs into closed trails.Czech. Math. J. 53 (2003), 127–134. MR 1962004, 10.1023/A:1022931710349 |
| Reference:
|
[10] Z. Kocková: Decomposition of even graphs into closed trails.Abstract at Grafy ’03, Javorná, Czech Republic. |
| Reference:
|
[11] J. Liu: The equipartite Oberwolfach problem with uniform tables.J. Combin. Theory, Ser. A 101 (2003), 20–34. Zbl 1015.05074, MR 1953278 |
| Reference:
|
[12] E. S. Mahmoodian and M. Mirzakhani: Decomposition of complete tripartite graphs into $5$-cycles.In: Combinatorics Advances, Kluwer Academic Publishers, Netherlands, 1995, pp. 235–241. MR 1366852 |
| Reference:
|
[13] D. Sotteau: Decomposition of $K_{m,n}(K^*_{m,n})$ into cycles (circuits) of length $2k$.J. Combinatorial Theory (Series B) 30 (1981), 75–81. Zbl 0463.05048, MR 0609596, 10.1016/0095-8956(81)90093-9 |
| . |
