<p>I am trying to track down the name of this digraph and some references:</p>

<p>You take all members of the transformation semigroup on $n$  elements, $T_{n}$.</p>

<p>For two members $x$ ,$y$ ; if $x$  is in the semigroup generated by y then you put an arrow from $y$  -> $x$ . You would read this as "$x$  is in the semigroup generated by $y$". Alternatively $y^k = x$.</p>

<p>What is the name of this digraph? References would be great.</p>

<p>If you wanted to visualize it, the symmetric group $S_{n}$ would be one of the connected components. The sinks are idemptent transformations like (0,1,2,3), (1,1,1,1), ... </p>

CC BY-SA 3.0
2013-04-19T19:58:21.060Z
Just found this article. Digraphs and the semigroup of all functions on a finite set, by Peter M. Higgins, Glasgow J. Math. 30 (1988), pp. 41-57
Chad Brewbaker
CC BY-SA 3.0
2013-04-19T20:06:22.267Z
This article isn't what I am looking for as the transformations are the vertices in my digraph, not the elements 0...n-1 as in this paper.
Chad Brewbaker
CC BY-SA 3.0
2013-04-22T10:03:12.427Z
I asked a question [Cayley graph of semigroups](http://math.stackexchange.com/q/113132/17111) on Math SE. I hope it would be somewhat helpful to you.
Nobody
CC BY-SA 3.0
2013-04-25T10:33:11.043Z
I've never heard of this digraph before, sorry.  It's quite a strange object.  Sure, $S_n$ is a connected component, but the only strongly connected components are the cyclic subgroups.  How did you come across this, and can you give me a reason to believe it's somehow a useful way of viewing $T_n$, or interesting for some other reason?
Tara B
CC BY-SA 3.0
2013-04-25T16:12:52.920Z
I am deriving combinatorial properties of this graph in the domain of software testing. If you know your state space is a semigroup $a->b$ means you don't have to test $b$ if you have already tested $a$. I hammered out a lot of properties for Sn, http://oeis.org/A186202 ; now I am tackling Tn. Before submitting it to a journal I wanted to get all the canonical semigroup terms correct.
Chad Brewbaker
CC BY-SA 3.0
2013-04-25T17:13:26.670Z
I am aware of the Green relation digraphs, but mine doesn't seem to be any of them: http://en.wikipedia.org/wiki/Green's_relations
Chad Brewbaker
CC BY-SA 3.0
2013-04-26T10:37:55.447Z
Ah, sorry, I only just saw this, because I wasn't notified of your reply.  What do you mean exactly by the 'Green relation digraphs'?  (The left and right Cayley graphs of a semigroup give you all the information about ${\cal R}$ and ${\cal L}$, but I haven't seen digraphs for the other Green's relations.)
Tara B
CC BY-SA 3.0
2013-05-15T15:12:20.913Z
The Green relations are the only other graph over the transformation semigroup I was aware of in the literature. I see no reason why you couldn't define the Green relation edges in terms of the digraph I am asking about since it should have all the information required in it's structure.
Chad Brewbaker
<graph-theory><automata-theory>
Name this digraph
Chad Brewbaker
# Name this digraph

(Asked by: username_0 on 2013-04-19)

I am trying to track down the name of this digraph and some references:

You take all members of the transformation semigroup on $n$ elements, $T\_{n}$.

For two members $x$ ,$y$ ; if $x$ is in the semigroup generated by y then you put an arrow from $y$ -> $x$ . You would read this as "$x$ is in the semigroup generated by $y$". Alternatively $y^k = x$.

What is the name of this digraph? References would be great.

If you wanted to visualize it, the symmetric group $S\_{n}$ would be one of the connected components. The sinks are idemptent transformations like (0,1,2,3), (1,1,1,1), ...

**Tags:** graph-theory, automata-theory

> **Comments:**
> **username_0**: Just found this article. Digraphs and the semigroup of all functions on a finite set, by Peter M. Higgins, Glasgow J. Math. 30 (1988), pp. 41-57  
> **username_0**: This article isn't what I am looking for as the transformations are the vertices in my digraph, not the elements 0...n-1 as in this paper.  
> **username_1**: I asked a question [Cayley graph of semigroups](http://math.stackexchange.com/q/113132/17111) on Math SE. I hope it would be somewhat helpful to you.  
> **username_2**: I've never heard of this digraph before, sorry.  It's quite a strange object.  Sure, $S_n$ is a connected component, but the only strongly connected components are the cyclic subgroups.  How did you come across this, and can you give me a reason to believe it's somehow a useful way of viewing $T_n$, or interesting for some other reason?  
> **username_0**: I am deriving combinatorial properties of this graph in the domain of software testing. If you know your state space is a semigroup $a->b$ means you don't have to test $b$ if you have already tested $a$. I hammered out a lot of properties for Sn, http://oeis.org/A186202 ; now I am tackling Tn. Before submitting it to a journal I wanted to get all the canonical semigroup terms correct.  
> **username_0**: I am aware of the Green relation digraphs, but mine doesn't seem to be any of them: http://en.wikipedia.org/wiki/Green's_relations  
> **username_2**: Ah, sorry, I only just saw this, because I wasn't notified of your reply.  What do you mean exactly by the 'Green relation digraphs'?  (The left and right Cayley graphs of a semigroup give you all the information about ${\cal R}$ and ${\cal L}$, but I haven't seen digraphs for the other Green's relations.)  
> **username_0**: The Green relations are the only other graph over the transformation semigroup I was aware of in the literature. I see no reason why you couldn't define the Green relation edges in terms of the digraph I am asking about since it should have all the information required in it's structure.  

---

## 0 answers

