Embedding path designs in 4-cycle systems
A \(G\)-design of order \(n\) is an edge-disjoint decomposition of \(K_n\) into copies of the graph \(G\). A path design \(P(n,s,1)\) is a \(P_s\)-design of order \(n\), where \(P_s\) is the path with \(s\) vertices (and length \(s-1\)). An \(m\)-cycle system is a \(C_m\)-design, where \(C_m\) is the cycle of length \(m\). We say that a path design \(P(v,s,1)\) defined on the vertex set \(\Omega\) is embedded in an \(m\)-cycle system defined on the vertex set \(W\), with \(\Omega \subseteq W\), if the decomposition induced by the vertex set \(\Omega\) starting from the \(m\)-cycle system gives the path design (and isolated vertices). In the current work, for each admissible \(n\), all integers \(v \geq 3\) are determined such that there exists a \(P(v,3,1)\) embedded in a \(4\)-cycle system of order \(n\). This extends earlier results by \textit{S. Milici} and the author [Discrete Math. 208/209, 443-449 (1999; Zbl 0930.05009)], where the additional requirement that the path design be a handcuffed design---meaning that each vertex must belong to the same number of paths---was imposed.
scientific article; zbMATH DE number 1838903