Independence and Matchings on Cayley Digraphs of Transformation Semigroups with Fixed Sets

Abstract

Let $Y$ be a nonempty set of $X$ and denote by $Fix(X,Y)$ a semigroup of full transformations $\alpha$ on $X$ provided that $a\alpha = a$ for all $a\in Y$. Further, let $A$ be a nonempty subset of $Fix(X,Y)$. The Cayley digraph $\text{Cay}(Fix(X,Y),A)$ is defined to be a digraph whose vertex set is $Fix(X,Y)$ and arc set is the set of all ordered pairs $(\alpha,\beta)$; where $\alpha, \beta\in Fix(X,Y)$, such that $\beta = \alpha\gamma$ for some $\gamma\in A$. A nonempty subset $I$ of $Fix(X,Y)$ is said to be independent if every two vertices in $I$ are independent, that is, there is no arc joining them. The maximum cardinality of an independent set is called the independence number. Moreover, an edge independent set is called a matching and the maximum cardinality of an edge independent set is called the matching number. In this paper, we determine several independence and matching parameters of Cayley digraphs of $Fix(X,Y)$ whose connection sets are relative to minimal idempotents and permutations.