On Cayley Graphs of Symmetric Inverse Semigroups

Abstract

Let ${\mathcal{I}}_X$ be the symmetric inverse semigroup on a finite nonempty set $X$, and let $A$ be a subset of ${\mathcal{I}}_X^{\ast }={\mathcal{I}}_X\setminus \{0\}$. Let $\text{Cay}({\mathcal{I}}_X^{\ast },A)$ be the graph obtained by deleting vertex $0$ from the Cayley graph $\text{Cay}({\mathcal{I}}_X,A)$. We obtain conditions on $\text{Cay}({\mathcal{I}}_X^{\ast },A)$ for it to be ${\text{ColAut}}_A({\mathcal{I}}_X^{\ast })$-vertex-transitive and ${\text{Aut}}_A({\mathcal{I}}_X^{\ast })$-vertex-transitive. The basic structure of vertex-transitive $\text{Cay}({\mathcal{I}}_X^{\ast },A)$ is characterized. We also investigate the undirected Cayley graphs of symmetric inverse semigroups, and prove that the generalized Petersen graph can be constructed as a connected component of a Cayley graph of a symmetric inverse semigroup, by choosing an appropriate connecting set.