On the Connectivity and Eulerian Properties of Cayley Digraphs in Transformation Monoids

Abstract

This paper establishes fundamental connections between the graph-theoretic properties of Cayley digraphs and the algebraic structure of transformation monoids. Our main contributions include a complete characterization of strong connectivity in transformation monoids, proving that for a transformation monoid T acting on a finite set X, the Cayley digraph Cay(T, S) with respect to a generating set S ⊆ T is strongly connected if and only if T contains the full symmetric group S(X); and a classification of Eulerian properties in symmetric groups, demonstrating that for the symmetric group S_n with any generating set S, the Cayley digraph Cay(S_n, S) is Eulerian precisely when it is strongly connected. We provide concrete examples illustrating these theorems, including detailed Cayley graph constructions for S₃ with explicit generating sets. Our results reveal deep connections between monoid theory and graph theory, showing how algebraic properties manifest in combinatorial structures. The proofs employ techniques from semigroup theory, algebraic graph theory, and finite group theory, offering new insights into the representation of transformation monoids through their generator-dependent digraphs. This work contributes to the broader understanding of how algebraic structures can be studied through their associated graphs.