Distance labelings: a generalization of Langford sequences

Abstract

A Langford sequence of order m and defect d can be identified with a labeling of the vertices of a path of order 2m in which each label from d up to d + m − 1 appears twice and in which the vertices that have been labeled with k are at distance k. In this paper, we introduce two generalizations of this labeling that are related to distances. The basic idea is to assign nonnegative integers to vertices in such a way that if n vertices (n > 1) have been labeled with k then they are mutually at distance k. We study these labelings for some well known families of graphs. We also study the existence of these labelings in general. Finally, given a sequence or a set of nonnegative integers, we study the existence of graphs that can be labeled according to this sequence or set.

The research conducted in this document by the first author has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and symbolically by the Catalan Research Council under grant 2014SGR1147.