Labeled Packing of Cycles and Circuits

In 2013, Duchçne, Kheddouci, Nowakowski and Tahraoui introduced a labeled version of the graph packing problem. It led to the introduction of a new graph parameter, the k-packing label-span λ^k. This parameter corresponds, given a graph H on n vertices, to the maximum number of labels we can assign to the vertices of the graph, such that there exists a packing of k copies of H into the complete graph K_n, coherent with the labels of the vertices. The authors intensively studied the labeled packing of cycles, and, among other results, they conjectured that for every cycle C_n of order n = 2k + x, with k ≥ 2 and 1 ≤ x ≤ 2k − 1, the value of λ^k(C_n) was 2 if x is 1 and k is even, and x + 2 otherwise. In this paper, we disprove this conjecture by giving a counterexample. We however prove that it gives a valid lower bound, and we give sufficient conditions for the upper bound to hold. We then give some similar results for the labeled packing of circuits.