Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
cycles; decomposing complete tripartite graphs
cycles; decomposing complete tripartite graphs
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$.
References:
[1] P. Balister: Packing circuits into $K_N$. Combinatorics, Probability and Computing 10 (2001), 463–499. DOI 10.1017/S0963548301004771 | MR 1869841 | Zbl 1113.05309
[2] P. Balister: Packing closed trails into dense graphs. J. Combinatorial Theory, Ser. B 88 (2003), 107–118. DOI 10.1016/S0095-8956(02)00039-4 | MR 1973263 | Zbl 1045.05074
[3] E. J. Billington: Decomposing complete tripartite graphs into cycles of length $3$ and $4$. Discrete Math. 197/198 (1999), 123–135. MR 1674855
[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 2041871 | Zbl 1056.05014
[5] N. J. Cavenagh: Decompositions of complete tripartite graphs into $k$-cycles. Australas. J. Combin. 18 (1998), 193–200. MR 1658341 | Zbl 0924.05051
[6] N. J. Cavenagh: Further decompositions of complete tripartite graphs into $5$-cycles. Discrete Math. 256 (2002), 55–81. MR 1927056 | Zbl 1009.05108
[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
[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 10.1007/s003730050003 | MR 1750460
[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 10.1023/A:1022931710349 | MR 1962004
[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 1953278 | Zbl 1015.05074
[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
[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 10.1016/0095-8956(81)90093-9 | MR 0609596 | Zbl 0463.05048
Search
Partner of
