Embedding path designs into a maximum packing of Kn with 4-cycles

摘要

A packing of Kn with copies of C4 (the cycle of length 4), is an ordered triple (V,C,L), where V is the vertex set of the complete graph Kn, C is a collection of edge-disjoint copies of C4, and L is the set of edges not belonging to a block of C. The number n is called the order of the packing and the set of unused edges L is called the teane. If C is as large as possible, then (V, C, L) is called a maximum pacfcinp MPC(n, 4,1). We say that a path design P(v, k, 1) (W, V) is embedded into an MPC(n,4,1) (V,C,L) if there is an injective such that P is a subgraph of f(P) for every denote the set of the integers v such that there exists an MPC(n,4,1) which embeds a P(v,k,1), If n ≡ 1 (mod 8) then an MPC(n,4,1) coincides with a 4-cycle system of order n and the related embedding problem is completely solved by Quattrocchi, Discrete Math., 255 (2002). Present paper is to determine SP(n, 4, k) for every integer n ≡ 1 (mod 8), n ≥ 4.