Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I did Google search and can't find a good answer. I thought I should ask experts here.

http://en.wikipedia.org/wiki/Cayley_graph is for groups. My question is,

Is there a special name for the Cayley graph of semigroups?

share|improve this question
Not as far as I know. The few times that I have seen this come up, people refer to it as the Cayley graph of the semigroup. –  Jim Belk Feb 25 '12 at 5:41

4 Answers 4

up vote 4 down vote accepted

We call them Cayley graphs (it doesn't seem to be usual to say 'Cayley digraph'), and they are interesting. I am doing research on semigroups, and quite often draw the Cayley graph of a semigroup to get an idea of what it's like. I don't know how much background on semigroups you have, but one reason Cayley graphs for semigroups are interesting is that the $\mathcal{R}$-classes in a semigroup correspond to the strongly connected components in its (right) Cayley graph.

share|improve this answer

The difference between a semigroup and a group is the existence of an identity and inverses and it are just those properties that make Cayley graphs interesting ( read: possible ). There are no Cayley graphs for semigroups.

share|improve this answer
To be fair, one may still speak of Cayley digraphs, and these may also be interesting. While your answer is strictly speaking correct, if you adopt the usual convention that graphs are undirected, it's a little uncharitable. –  Niel de Beaudrap Feb 25 '12 at 12:02

If you want to have a group theory approach, then you are right. These graphs are not interesting! However if you have a semigroup background and you know about automaton and semiautomaton, you can find these graphs very interesting (see Kilp and Knauer's book). So the second answer is not very correct and fair since the identity and inverse elements are not very good in semigroups because they make everything very similar to groups.

I completely accept that inverse semigroups (or much better, Clifford semigroups which are the semilattice of groups) are very interesting and important, and I never claim that they are not good. I told they are very similar to groups and exactly for this reason, the behavior of these Cayley graphs and required techniques are similar to the Cayley graphs of groups (but not exactly the same). However when you work with semigroups which are too far from groups (like bands), the behavior and the required techniques are very interesting because most of the time, they are not available in Group Theory and this causes a value for the independent study of Cayley graphs of semigroups and a difference between Cayley graphs of groups and semigroups.

For Tara B: Based on where you study, I think that R. Gray's works must be interesting for you and it can show you some other applications and importance of Cayley graphs of semigroups. Also I strongly suggest you to see " Generalized Cayley graphs of semigroups" in Semigroup Forum.

share|improve this answer
Thanks for the info of Kilp and Knauer's book. I did not know that book. However, I am not that interested in wreath product. Do you happen to know some info about direct product of semiautomata? Thanks again. –  scaaahu Feb 28 '13 at 2:48
I don't agree that inverse elements are 'not very good in semigroups'. Inverse semigroups (semigroups in which every element has a unique inverse) are interesting semigroups which are still quite far from being groups. –  Tara B Mar 2 '13 at 13:56
@Benham: You can merge your current account with the one you used to post this answer originally by doing this: From any page footer -> 'contact us' >> 'Merge user profiles' –  Zev Chonoles Mar 2 '13 at 20:03
@ZevChonoles: Sorry I rolled back the edit because I thought it was a different user... –  Thomas Mar 2 '13 at 20:05
@Thomas: No worries, that's completely understandable. I've rolled back the rollback :) –  Zev Chonoles Mar 2 '13 at 20:06

You can consider every semiautomaton as an S-act, when S is a monoid.


(Kilp and Knauer's book, on Page 45) So the answer of your question can be found in the same book on Page 104.


Good luck

share|improve this answer
Thank you. I am not sure if you and user64269 are the same person. Thanks to both of you. I'll get the book. –  scaaahu Mar 2 '13 at 10:05
Sorry, I should have verified my e-mail address before. –  Behnam Mar 2 '13 at 10:13
You can flag the moderator to merge your two accounts into one. –  scaaahu Mar 2 '13 at 10:42
@Behnam: This doesn't appear to be an answer to the question about Cayley graphs. (It's not really a problem in this case, but generally 'answers' should be answers to the question they are posted as answers to.) It would probably have been better to add this to your original answer, as it was the answer to a question asked by scaahu in response to that answer. –  Tara B Mar 2 '13 at 13:52
You are right but I am not very familiar with this site. I try to fix it. –  Behnam Mar 2 '13 at 19:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.