Distance labellings of Cayley graphs of semigroups (Q906971): Difference between revisions

First note that in this paper the term graph means a finite directed graph without multiple edges, but possibly with loops. Recall that for a semigroup \(S\), and a non-empty subset \(C\) of \(S\), the Cayley graph \(\mathrm{Cay}(S, C)\) of \(S\) with connection set \(C\) is defined as the graph with vertex set \(S\) and edge set \(E=E(S, C)\) consisting of those ordered pairs \((u, v)\) such that \(cu=v\) for some \(c\in C\). If the adjacency relation of \(\mathrm{Cay}(S, C)\) is symmetric, then it becomes an undirected graph (for more details about undirected Cayley graphs of semigroups see [\textit{A. V. Kelarev}, Australas. J. Comb. 25, 73--78 (2002; Zbl 0993.05085)]). Note that all theorems in this paper will involve undirected Cayley graphs only. Let \(\mathbb{N}\) be the set of all positive integers, and let \(k_1, k_2,\dots, k_l\in \mathbb{N}\) for some \(1\leq l\). A distance labelling, or an \(L(k_1, k_2,\dots , k_l)\)-labelling, of an undirected graph \(\Gamma = (V, E)\) is a mapping \(f:V\to \mathbb{N}\) such that \(|f(u)-f(v)|\geq k_t\) for \(t= 1, 2,\dots, l\) and any \(u, v\in V\) with \(d(u, v) =t\), where \(d(u, v)\) is the distance between \(u\) and \(v\) in \(\Gamma\). The integer \(f(v)\) is called the label assigned to \(v\) under \(f\), and the difference between the largest and the smallest labels is called the \textit{span} of \(f\). The minimum span over the set of all \(L(k_1, k_2,\dots , k_l)\)-labellings of \(\Gamma\) is denoted by \(\lambda_{k_1, k_2,\dots , k_l}(\Gamma)\). Finally recall that a semigroup is said to be combinatorial if all of its subgroups are singletons. First, the authors try to connect the algebraic properties of a semigroup, to the graph theoretical properties of the spans of Cayley graphs of that semigroup. We state some shortened versions of their main theorems about this view of point in the following. Theorem 1. For any finite semigroup \(S\), the following conditions are equivalent: {\parindent=0.7cm\begin{itemize}\item[(i)] \(S\) is combinatorial; \item[(ii)] for each nonempty subsemigroup \(T\) of \(S\) and every nonempty subset \(C\) of \(T\), if \(\mathrm{Cay}(T, C)\) is undirected, then the equality \[ \lambda_{k_1, k_2,\dots, k_l}(\mathrm{Cay}(T, C)) = (|Cc|-1)k_1 \] holds for every integer \(l > 1\), all \(k_1,\dots , k_l\in \mathbb{N}\), and every element \(c\) in \(C\). \end{itemize}} Theorem 2. For any finite semigroup \(S\), the following conditions are equivalent: {\parindent=0.7cm\begin{itemize}\item[(i)] \(S\) is a right zero band; \item[(ii)] for each nonempty subset \(C\) of \(S\), \(\mathrm{Cay}(S, C)\) is undirected and the equality \[ \lambda_{k_1, k_2,\dots , k_l}(\mathrm{Cay}(T, C)) = (|Cc|-1)k_1 \] holds for every integer \(l > 1\), all \(k_1,\dots , k_l\in \mathbb{N}\), and every element \(c\) in \(C\). \end{itemize}} On the other hand, the authors try to connect the graph-theoretical assumptions on the Cayley graphs of semigroups to the algebraic properties of the semigroups. We state one of their main results about this point of view. Theorem 3. For any semigroup \(S\) and any nonempty subset \(C\) of \(S\), the following conditions are equivalent: {\parindent=0.7cm\begin{itemize}\item[(i)] \(CS =S\), \(\langle C\rangle\) is a completely simple semigroup, and for each \(c\in C\), the set \(Cc\) is a left group and a left ideal of \(\langle C \rangle\); \item[(ii)] \(\mathrm{Cay}( S, C)\) is undirected, and for every integer \(l >1\) and all \(k_1,\dots , k_l\in \mathbb{N}\), the equality \[ \lambda_{k_1, k_2,\dots , k_l}(\mathrm{Cay}(T, C)) = (|Cc|-1)k_1 \] holds for all elements \(c\) of \(C\); \item[(iii)] \(\mathrm{Cay}(S, C)\) is a disjoint union of complete graphs. \end{itemize}} Finally in the last main result of the paper, the authors describe all graphs whose minimum spans satisfy some of the restrictions that occur in the previous theorems. Theorem 4. For any finite undirected graph \(\Gamma = (V, E)\), the following conditions are equivalent: {\parindent=0.7cm\begin{itemize}\item[(i)] There exist a function \(F:\mathbb{N}\to \mathbb{N}\) and an integer \(l > 1\) such that for all \(k_1, k_2,\dots, k_l\in \mathbb{N}\), the minimum span of \(\Gamma\) is determined by the formula \[ \lambda_{k_1, k_2,\dots , k_l}(\mathrm{Cay}(T, C)) =F(k_1); \] \item[(ii)] \(\Gamma\) is a disjoint union of complete graphs. \end{itemize}}