### 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)

Speaker

Nick Cavenagh

Research Area
Affiliation

University of Waikato

Date

Tue, 08/07/2014 - 12:00pm

Venue

RC-4082, The Red Centre, UNSW