pipette
ENEnglish

On Multi-label radio Labelings of Graphs

Olivier Togni

Preprint

En palabras de los autores

We propose and study a multi-labeling generalization of the -radio labeling problem of graphs: given a graph and integers and , assign to each vertex of a set of integer labels such that distinct labels assigned to a vertex differ by at least , and the labels of any two distinct vertices and pairwise differ by at least , with being the distance between vertices and . We prove general bounds on the minimum span of such a labeling and more refined results for the case . For paths and cycles, we derive sharp bounds on the minimum span when is small. We finally propose a conjecture for the minimum span on the path and for an almost-tight bound on the cycle.

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 14 pages