Geodesic
Labeled Packing of Cycles and Circuits
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 443-469

Voir la notice de l'article provenant de la source Library of Science

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 Kn, 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 Cn of order n = 2k + x, with k ≥ 2 and 1 ≤ x ≤ 2k − 1, the value of λk(Cn) 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.
Keywords: packing of graphs, labeled packing, cycles, circuits 
@article{DMGT_2022_42_2_a7,
     author = {Joffard, Alice and Kheddouci, Hamamache},
     title = {Labeled {Packing} of {Cycles} and {Circuits}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {443--469},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a7/}
}
TY  - JOUR
AU  - Joffard, Alice
AU  - Kheddouci, Hamamache
TI  - Labeled Packing of Cycles and Circuits
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 443
EP  - 469
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a7/
LA  - en
ID  - DMGT_2022_42_2_a7
ER  - 
%0 Journal Article
%A Joffard, Alice
%A Kheddouci, Hamamache
%T Labeled Packing of Cycles and Circuits
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 443-469
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a7/
%G en
%F DMGT_2022_42_2_a7
Joffard, Alice; Kheddouci, Hamamache. Labeled Packing of Cycles and Circuits. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 443-469. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a7/