Minimum embedding of balanced \(P_{4}\)-designs into 5-cycle systems. (Q1428541): Difference between revisions

A decomposition of \(K_v\) into \(P_4\)s so that every vertex belongs to the same number of \(P_4\)s is a {balanced \(P_4\)-design}. For some number \(v+w\), there is a decomposition of \(K_{v+w}\) into 5-cycles, so that restricting to chosen \(v\) vertices, we obtain the \(P_4\)-design; the 5-cycle system {embeds} the \(P_4\)-design. What is the smallest value of \(w\) so that some balanced \(P_4\)-design of order \(v\) can be embedded in a 5-cycle system of order \(v+w\)? It is shown that the minimum value of \(w\) is \((v-1)/3\) when \(v \equiv 4,16 \pmod{30}\), \((v+5)/3\) when \(v \equiv 7,10,22,25 \pmod{30}\), \((v+11)/3\) when \(v \equiv 1,13,28 \pmod{30}\), and \((v+17)/3\) when \(v \equiv 19 \pmod{30}\).