Minimal Paths in the Commuting Graphs of Semigroups

European Journal of Combinatorics, 32 (2011), 178-197
http://dx.doi.org/10.1016/j.ejc.2010.09.004

Let S be a finite non-commutative semigroup. The commuting graph of S, denoted G(S), is the graph whose vertices are the non- central elements of S and whose edges are the sets {a, b} of vertices such that a \neq b and ab = ba. Denote by T(X) the semigroup of full transformations on a finite set X . Let J be any ideal of T (X ) such that J is different from the ideal of constant transformations on X. We prove that if |X| ? 4, then, with a few exceptions, the diameter of G(J ) is 5. On the other hand, we prove that for every positive integer n, there exists a semigroup S such that the diameter of G(S) is n.
We also study the left paths in G(S), that is, paths a1 ? a2 ? ··· ? am such that a1 ?= am and a1ai = amai for all i ? {1,...,m}. We prove that for every positive integer n ? 2, except n = 3, there exists a semigroup whose shortest left path has length n. As a corollary, we use the previous results to solve a purely algebraic old problem posed by B.M. Schein.