Anthony HILTON

(University of Reading, UK)

Embedding partial 4-cycle systems

A partial 4-cycle system is a simple graph whose edge set is decomposed into edge-disjoint 4-cycles. If the graph is complete then we have a 4-cycle system. The order of a partial 4-cycle system is the number of vertices in the graph. The question we consider is this: Given a partial 4-cycle system $S$ of order n, how many extra vertices must you introduce for it to be possible to extend $S$ to a 4-cycle system $T$, where the vertex set of $T$ is the vertex set of $S$ plus the extra vertices? More precisely, given n what is the value of t such that any partial 4-cycle system of order n can be embedded in a 4-cycle system $T$ of order t. It has been known for a long while that the order of $T$ is at least $n + \sqrt{n}$. We show that it is at most $n + \sqrt{12}n^{\frac{3}{4}}$. This improves on the previous best estimate of $2n + 16$.

Serdecznie zapraszamy wszystkich chêtnych !