Originator(s): H. L. Fu (presented by Chayapa Darayon - REGS 2009)
Definitions: An m-cycle system of G is an ordered pair (G,C) such that G is a graph and C is a set of m-cycles whose edges partition E(G); that is, C is a decomposition of G into cycles of length m. The leave of an m-cycle system (G,C) (relative to Kn) is the graph obtained by deleting E(G) from Kn (note that G may have fewer than n vertices. A forest F is odd if every vertex of F has odd degree.
Background: There have been many results on m-cycle decompositions of complete graphs and complete bipartite graphs. The problem of finding the pairs (m,n) such that Kn has an m-cycle decomposition was completely solved by Alspach and Gavlas [AG] and by Sajna [S]. For example, when m is odd, such a decomposition exists if and only if the obvious necessary condition that n(n-1)/2 be divisible by m is satisfied. The case of even m is more complicated.
More generally, one can seek an m-cycle system with a specified leave H in Kn. Alspach and Gavlas [AG] completely solved the problem when H is a 1-factor. When H is a 2-factor the problem has been solved for m∈{3,4,n} [B,CR,FR2].
Conjecture: If F is an odd forest of even order n, and m divides the number of edges in Kn-E(F) (and m≥3), then Kn-E(F) has an m-cycle decomposition.
Comments: Using inductive methods, Fu and Rodger [FR1] proved the conjecture for m=4, and for m=6 it was proved by Ashe, Fu and Rodger [AFR].
References:
[AFR] D.J. Ashe, H.L. Fu and C.A. Rodger, A solution to the forest leave problem for partial 6-cycle systems, Discrete Math. 281 (2004) 27-41.
[AG] B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn-I, J. Combin. Theory (B) 81 (2001) 77-99.
[B] H. Buchanan, Ph.D. dissertation, Univ West Virginia, 1996.
[CR] C.J. Colbourn and A. Rosa, Quadratic leaves of maximal partial triple systems, Graphs Combin 2 (1986) 317-337.
[FR1] H.L. Fu and C.A. Rodger, Forest leaves and four cycles, J. Graph Theory 33 (2000) 161-166.
[FR2] H.L. Fu and C.A. Rodger, Four-cycle systems with two-regular leaves, Graphs Combin. 7 (2001) 457-461
[S] M. Sajna, Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Des. 10 (2002) 27-78.