Article in volume
Authors:
Title:
Labeled packing of cycles and circuits
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 443-469
Received: 2018-06-09 , Revised: 2019-11-26 , Accepted: 2019-11-26 , Available online: 2020-01-15 , https://doi.org/10.7151/dmgt.2290
Abstract:
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 $\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.
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.
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
References:
- B. Alspach, The wonderful Walecki construction, Bull. Inst. Combin. Appl. 52 (2008) 7–20.
- 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 - 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 - E. Duchene, H. Kheddouci, R.J. Nowakowski and M.A. Tahraoui, Labeled packing of graphs, Australas. J. Combin. 57 (2013) 109–126.
- 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 - 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 - 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 - 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 - M.A. Tahraoui, Coloring, Packing and Embedding of Graphs (Ph.D. Thesis, 2012).
- 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 - 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 - 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 - 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
Close