2015/09/03 by Andrei Kelarev, Kelarev, Andrei, Charl Ras +3
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Theory Research #Fuzzy and Soft Set Theory #math.CO #math.GR #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1509.00924
arxiv created 2015/09/03 · arxiv updated 2015/09/04
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 \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 \Cay(S,C). We then describe all graphs with minimum spans satisfying the same restrictions, and give examples to show that a fairly straightforward upper bound for the minimum spans of the underlying undirected graphs of Cayley graphs turns out to be sharp even for the class of combinatorial semigroups.