Labeled Packing of Cycles and Circuits

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 λ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.

Keywords

• packing of graphs
• labeled packing
• cycles
• circuits
• 05c70
• 05c38