Distance labellings of Cayley graphs of semigroups

Abstract

This paper establishes connections between the structure of a semigroup and the minimum spans of distance labellings of its Cayley graphs. We show that certain general restrictions on the minimum spans are equivalent to the semigroup being combinatorial, and that other restrictions are equivalent to the semigroup being a right zero band. We obtain a description of the structure of all semigroups S and their subsets C such that $$\,{\mathrm {Cay}}(S,C)$$Cay(S,C) is a disjoint union of complete graphs, and show that this description is also equivalent to several restrictions on the minimum span of $$\,{\mathrm {Cay}}(S,C)$$Cay(S,C). We then describe all graphs w..