Decomposing complete tripartite graphs into closed trails of arbitrary lengths

Elizabeth J. Billington; Nicholas J. Cavenagh

Czechoslovak Mathematical Journal (2007)

  • Volume: 57, Issue: 2, page 523-551
  • ISSN: 0011-4642

Abstract

top
The complete tripartite graph K n , n , n has 3 n 2 edges. For any collection of positive integers x 1 , x 2 , ⋯ , x m with ∑ i = 1 m x i = 3 n 2 and x i ≥ 3 for 1 ≤ i ≤ m , we exhibit an edge-disjoint decomposition of K n , n , n into closed trails (circuits) of lengths x 1 , x 2 , ⋯ , x m .

How to cite

top

Billington, Elizabeth J., and Cavenagh, Nicholas J.. "Decomposing complete tripartite graphs into closed trails of arbitrary lengths." Czechoslovak Mathematical Journal 57.2 (2007): 523-551. <http://eudml.org/doc/31145>.

@article{Billington2007,
abstract = {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$.},
author = {Billington, Elizabeth J., Cavenagh, Nicholas J.},
journal = {Czechoslovak Mathematical Journal},
keywords = {cycles; decomposing complete tripartite graphs; cycles; decomposing complete tripartite graphs; edge disjoint decomposition},
language = {eng},
number = {2},
pages = {523-551},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Decomposing complete tripartite graphs into closed trails of arbitrary lengths},
url = {http://eudml.org/doc/31145},
volume = {57},
year = {2007},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 57
IS - 2
SP - 523
EP - 551
AB - 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$.
LA - eng
KW - cycles; decomposing complete tripartite graphs; cycles; decomposing complete tripartite graphs; edge disjoint decomposition
UR - http://eudml.org/doc/31145
ER -

References

top
  1. 10.1017/S0963548301004771, Combinatorics, Probability and Computing 10 (2001), 463–499. (2001) Zbl1113.05309MR1869841DOI10.1017/S0963548301004771
  2. 10.1016/S0095-8956(02)00039-4, J. Combinatorial Theory, Ser. B 88 (2003), 107–118. (2003) Zbl1045.05074MR1973263DOI10.1016/S0095-8956(02)00039-4
  3. Decomposing complete tripartite graphs into cycles of length 3 and 4 , Discrete Math. 197/198 (1999), 123–135. (1999) MR1674855
  4. 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. (2003) Zbl1056.05014MR2041871
  5. Decompositions of complete tripartite graphs into k -cycles, Australas. J. Combin. 18 (1998), 193–200. (1998) Zbl0924.05051MR1658341
  6. Further decompositions of complete tripartite graphs into 5 -cycles, Discrete Math. 256 (2002), 55–81. (2002) Zbl1009.05108MR1927056
  7. On decomposing complete tripartite graphs into 5 -cycles, Australas. J. Combin. 22 (2000), 41–62. (2000) MR1795321
  8. 10.1007/s003730050003, Graphs and Combinatorics 16 (2000), 49–65. (2000) MR1750460DOI10.1007/s003730050003
  9. 10.1023/A:1022931710349, Czech. Math. J. 53 (2003), 127–134. (2003) MR1962004DOI10.1023/A:1022931710349
  10. Decomposition of even graphs into closed trails, Abstract at Grafy ’03, Javorná, Czech Republic. 
  11. The equipartite Oberwolfach problem with uniform tables, J. Combin. Theory, Ser. A 101 (2003), 20–34. (2003) Zbl1015.05074MR1953278
  12. Decomposition of complete tripartite graphs into 5 -cycles, In: Combinatorics Advances, Kluwer Academic Publishers, Netherlands, 1995, pp. 235–241. (1995) MR1366852
  13. 10.1016/0095-8956(81)90093-9, J. Combinatorial Theory (Series B) 30 (1981), 75–81. (1981) Zbl0463.05048MR0609596DOI10.1016/0095-8956(81)90093-9

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.