- Tytuł:
- Labeled Packing of Cycles and Circuits
- Autorzy:
-
Joffard, Alice
Kheddouci, Hamamache - Powiązania:
- https://bibliotekanauki.pl/articles/32361725.pdf
- Data publikacji:
- 2022-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
packing of graphs
labeled packing
cycles
circuits - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 443-469
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł