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/

[1] B. Alspach, The wonderful Walecki construction, Bull. Inst. Combin. Appl. 52 (2008) 7–20.

[2] B. Alspach, H. Gavlas, M. Šajna and H. Verrall, Cycle decompositions IV : complete directed graphs and fixed length directed cycles, J. Combin. Theory Ser. A 103 (2003) 165–208. https://doi.org/10.1016/S0097-3165(03)00098-0

[3] B. Bollobás and S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory Ser. B 25 (1978) 105–124. https://doi.org/10.1016/0095-8956(78)90030-8

[4] E. Duchene, H. Kheddouci, R.J. Nowakowski and M.A. Tahraoui, Labeled packing of graphs, Australas. J. Combin. 57 (2013) 109–126.

[5] A. Kaneko and K. Suzuki, Packing two copies of a tree into its third power, Discrete Math. 306 (2006) 2779–2785. https://doi.org/10.1016/j.disc.2006.04.019

[6] H. Kheddouci, J.-F. Saclé and M. Woźniak, Packing two copies of a tree into its fourth power, Discrete Math. 213 (2000) 169–178. https://doi.org/10.1016/S0012-365X(99)00177-6

[7] H. Kheddouci, S. Marshall, J.-F. Saclé and M. Woźniak, On the packing of three graphs, Discrete Math. 236 (2001) 197–225. https://doi.org/10.1016/S0012-365X(00)00443-X

[8] N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory Ser. B 25 (1978) 295–302. https://doi.org/10.1016/0095-8956(78)90005-9

[9] M.A. Tahraoui, Coloring, Packing and Embedding of Graphs (Ph.D. Thesis, 2012).

[10] M.A. Tahraoui, E. Duchêne and H. Kheddouci, Labeled 2 -packings of trees, Discrete Math. 338 (2015) 816–824. https://doi.org/10.1016/j.disc.2014.12.015

[11] M.A. Tahraoui, E. Duchêne and H. Kheddouci, Labeled embedding of ( n, n − 2)- graphs in their complements, Discuss. Math. Graph Theory 37 (2017) 1015–1025. https://doi.org/10.7151/dmgt.1977

[12] M. Woźniak, Packing of graphs and permutations—a survey, Discrete Math. 276 (2004) 379–391. https://doi.org/10.1016/S0012-365X(03)00296-6

[13] H.P. Yap, Packing of graphs—a survey, Ann. Discrete Math. 38 (1988) 395–404. https://doi.org/10.1016/S0167-5060(08)70809-4