ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


A. Joffard and H. Kheddouci


Labeled packing of cycles and circuits


Discussiones Mathematicae Graph Theory

Received: 2018-06-09, Revised: 2019-11-26, Accepted: 2019-11-26,


In 2013, Duch\c{e}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 $\lambda^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.<br>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\geq 2$ and $1\leq x \leq 2k-1$, the value of $\lambda^k(C_n)$ was $2$ if $x$ is $1$ and $k$ is even, and $x+2$ otherwise.<br>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.<br>We then give some similar results for the labeled packing of circuits


packing of graphs, labeled packing, cycles, circuits