Embedding path designs into a maximum packing of Kn with 4-cycles
Abstract
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 leave. If C is as large as possible, then (V, C, L) is called a maximum packing MPC(n, 4, 1). We say that a path design P (v, k, 1) (W, P) is embedded into an M PC(n, 4, 1) (V, C, L) if there is an injective mapping f : P → C such that P is a subgraph of f(P) for every P ∈ P. Let SP(n, 4, k) denote the set of the integers v such that there exists an M PC(n, 4, 1) which embeds a P(v,k, 1). If n ≡ 1 (mod 8) then an M PC(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). The aim of the present paper is to determine SP(n, 4, k) for every integer n ≢ 1 (mod 8), n ≥ 4.
