Geodesic
Decomposing complete tripartite graphs into closed trails of arbitrary lengths
Czechoslovak Mathematical Journal, Tome 57 (2007) no. 2, pp. 523-551 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
Classification : 05C38, 05C70
Keywords: cycles; decomposing complete tripartite graphs 
@article{CMJ_2007_57_2_a1,
     author = {Billington, Elizabeth J. and Cavenagh, Nicholas J.},
     title = {Decomposing complete tripartite graphs into closed trails of arbitrary lengths},
     journal = {Czechoslovak Mathematical Journal},
     pages = {523--551},
     year = {2007},
     volume = {57},
     number = {2},
     mrnumber = {2337613},
     zbl = {1174.05100},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2007_57_2_a1/}
}
TY  - JOUR
AU  - Billington, Elizabeth J.
AU  - Cavenagh, Nicholas J.
TI  - Decomposing complete tripartite graphs into closed trails of arbitrary lengths
JO  - Czechoslovak Mathematical Journal
PY  - 2007
SP  - 523
EP  - 551
VL  - 57
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2007_57_2_a1/
LA  - en
ID  - CMJ_2007_57_2_a1
ER  - 
%0 Journal Article
%A Billington, Elizabeth J.
%A Cavenagh, Nicholas J.
%T Decomposing complete tripartite graphs into closed trails of arbitrary lengths
%J Czechoslovak Mathematical Journal
%D 2007
%P 523-551
%V 57
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2007_57_2_a1/
%G en
%F CMJ_2007_57_2_a1
Billington, Elizabeth J.; Cavenagh, Nicholas J. Decomposing complete tripartite graphs into closed trails of arbitrary lengths. Czechoslovak Mathematical Journal, Tome 57 (2007) no. 2, pp. 523-551. http://geodesic.mathdoc.fr/item/CMJ_2007_57_2_a1/

[1] P. Balister: Packing circuits into $K_N$. Combinatorics, Probability and Computing 10 (2001), 463–499. | DOI | MR | Zbl

[2] P. Balister: Packing closed trails into dense graphs. J. Combinatorial Theory, Ser. B 88 (2003), 107–118. | DOI | MR | Zbl

[3] E. J. Billington: Decomposing complete tripartite graphs into cycles of length $3$ and $4$. Discrete Math. 197/198 (1999), 123–135. | MR

[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. | MR | Zbl

[5] N. J. Cavenagh: Decompositions of complete tripartite graphs into $k$-cycles. Australas. J. Combin. 18 (1998), 193–200. | MR | Zbl

[6] N. J. Cavenagh: Further decompositions of complete tripartite graphs into $5$-cycles. Discrete Math. 256 (2002), 55–81. | MR | Zbl

[7] N. J. Cavenagh and E. J. Billington: On decomposing complete tripartite graphs into $5$-cycles. Australas. J. Combin. 22 (2000), 41–62. | MR

[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. | DOI | MR

[9] M. Horňák and M. Woźniak: Decomposition of complete bipartite even graphs into closed trails. Czech. Math. J. 53 (2003), 127–134. | DOI | MR

[10] Z. Kocková: Decomposition of even graphs into closed trails. Abstract at Grafy ’03, Javorná, Czech Republic.

[11] J. Liu: The equipartite Oberwolfach problem with uniform tables. J. Combin. Theory, Ser. A 101 (2003), 20–34. | MR | Zbl

[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

[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. | DOI | MR | Zbl