Distance labelings : a generalization of Langford sequences

english

2017

volume 12, issue 2

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

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.

29.05.2020