A GRAPH-THEORETIC STUDY OF TRANSFORMATIONS WITH ORDER-PRESERVING ANDCONTRACTION RESTRICTIONS ON A FINITE CHAIN

Abstract

Every transformation α ∈ Tₙ naturally defines a directed graph, called the functional digraph of α, whose vertex set is Xₙ = {1, 2,…, n} and whose edge set is Eα = {(x, α(x)): x ∈ Xₙ}. Using this representation, we investigate a class of transformations whose associated digraphs satisfy different structural conditions on complementary subsets of the vertex set. For a fixed subset Y ⊆ Xₙ, we consider the set K= {α ∈ Tₙ:α|Y is Order-Preserving and α|Xₙ\Y is a contraction}. From a graph-theoretic perspective, this corresponds to functional digraphs whose induced subdigraph on Y preserves the chain's natural order, while the induced subdigraph on Xₙ\Y satisfies a distance-nonincreasing condition. We show that a transformation belongs to K if and only if these graph properties hold on the corresponding induced subdigraphs. Furthermore, the functional digraph of each element of K admits a natural decomposition into two components: an Order-Preserving digraph on Y and a contraction digraph on Xₙ\Y. We prove that the set K is closed under composition and therefore forms a subsemigroup of Tₙ when viewed through the composition of their associated functional digraphs. In addition, we characterize the idempotent elements of K in graph-theoretic terms by showing that α is idempotent if and only if every vertex in Γ(α) maps to a fixed point after one step. These results provide a graph-theoretic framework for studying hybrid classes of transformations on finite chains and contribute to the understanding of structural properties of functional digraphs arising from constrained transformations.