A Graph-Theoretic Characterisation of Generating Sets in Finite Full Transformation Semigroups

Abstract

 This paper investigates the structural characterization of generating sets within the semigroup of full transformations, emphasizing the graph-theoretic proper- ties of their associated digraphs. Focusing on the Jn−1-class, denoted by Jn−1 = {α ∈ Tn: | im(α)| = n − 1}, we establish necessary and sufficient conditions for a subset A ⊆ Dn−1 to be a generating set. It is proved that A generates Dn−1 if and only if A is a cover and the corresponding digraph ΓA is strongly connected. Consequently, minimal generating sets are precisely the minimal strongly connected covers of Dn−1. Furthermore, every generating subset induces a connected and cyclic digraph, thereby revealing intrinsic links between algebraic generation and graph connectivity. Illustrative examples for n = 4 and n = 5 are presented through egg-box diagrams and directed graphs, showing that six and ten elements, respectively, suffice to generate the semigroup. These values correspond to the Stirling numbers of the second kind, which determine the number of partitions required to cover the associated transformation graphs in Singn. The results provide a deeper understanding of the combinatorial and graph-theoretic structure of generating systems in finite full transformation semigroups