Generalized Cayley graphs of semigroups. II. (Q415532): Difference between revisions

Let \(T\) be an ideal extension of a semigroup \(S\) and \(\rho\subseteq T^1\times T^1\). Recall that the generalized Cayley graph \(\text{Cay}(S,\rho)\) of \(S\) relative to \(\rho\) is defined as the graph with vertex set \(S\) and edge set \(E(\text{Cay}(S,\rho))\) consisting of those ordered pairs \((a,b)\), where \(xay=b\) for some \((x,y)\in\rho\). In this paper, the author continues her study of the generalized Cayley graph of a semigroup which was introduced by her in part I [\textit{Y. Zhu}, Semigroup Forum 84, No. 1, 131-143 (2012; Zbl 1252.20052)]. As the main part of the paper, the author investigates some combinatorial property of generalized Cayley graphs and considers the following question ``which graphs are generalized Cayley graphs of some semigroup?''. For the latter, the author proves that some family of fission graphs and \(k\)-partite complete chain graphs with loops are generalized Cayley graphs of some semigroups. For the first, the author considers the \(D\)-saturated property of semigroups. This notion was introduced by \textit{A. V. Kelarev} and \textit{S. J. Quinn} [J. Algebra 251, No. 1, 16-26 (2002; Zbl 1005.20043)] and latter was investigated by Yang and Gao. Recall that a semigroup \(S\) is said to be \(D\)-saturated with respect to a subset \(T\) of \(S\) if for all infinite subsets \(V\) of \(S\), there exists a subgraph of \(\text{Cay}(S,T)\) isomorphic to \(D\) with all vertices in \(V\). The author generalizes most of the results proved for Cayley graphs of semigroups by Kelarev and Quinn and Yang and Gao to the generalized Cayley graphs of semigroups and she proves the following main results: Theorem. Assume that \(D\) is a finite simple graph with no cycle, \(T\) is an ideal extension of an infinite semigroup \(S\) and \(\rho\subseteq T^1\times T^1\) is a nonempty relation. Then the following conditions are equivalent: (i) \(S\) is Cayley \(D\)-saturated with respect to \(\rho\); (ii) every infinite subset of \(V(\text{Cay}(S,\rho))\) induces a subgraph of \(\text{Cay}(S,\rho)\) which is not null. Theorem. Assume that \(D\) is a finite simple graph which has a cycle, \(T\) is an ideal extension of an infinite semigroup \(S\) and \(\rho\subseteq T^1\times T^1\) is a nonempty relation. Then the following conditions are equivalent: (i) \(S\) is Cayley \(D\)-saturated with respect to \(\rho\); (ii) every subgraph of \(\text{Cay}(S,\rho)\) induced by an infinite subset of \(S\) contains a subgraph isomorphic to \(K_\infty\).