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 = \mathcal{I}_X \setminus \{0\}\). Let \(\text{Cay}(\mathcal{I}^*_X, 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, A)\) for it to be \(\text{ColAut}_A(\mathcal{I}^*_X)\)-vertex-transitive and \(\text{Aut}_A(\mathcal{I}^*_X)\)-vertex-transitive. The basic structure of vertex-transitive \(\text{Cay}(\mathcal{I}^*_X, 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.