Decomposition thresholds for cycles

Abstract:

A graph G decomposes into a graph H is there is a set of subgraphs of G, each isomorphic to H, which partition the edges of G. Even if H has as few as three edges, the question, ``Does G decompose into H?'' is NP-complete. However, if we know that G has high minimum degree, large order and satisfies certain elementary necessary conditions, we may guarantee a decomposition. To this end, the {\em decomposition threshold} g(H) of a graph H describes the minimum constant c such that if H has minimum degree cn+o(n) (and satisifes some necessary conditions), then G decomposes into H. Yuster (2002) showed that if H is bipartite and has a vertex of degree 1, then G(H)=1/2, which is optimal. However, if H is a 4-cycle, G(H)\geq 3/5.

We present some new results on decomposition thresholds for cycles.

(Joint work with Darryn Bryant and Benjamin R. Smith, University of Queensland)