Graphs and ranks of monoids

ABSTRACT

For a finite monoid S, let ν(S) (ν_d(S)) denote the least number n such that there exists a graph (directed graph) Γ of order n with End(Γ)≅S. Also let rank(S) be the smallest number of elements required to generate S. In this paper, we use Cayley digraphs of monoids, to connect lower bounds of ν(S) (ν_d(S)) to the lower bounds of rank(S). On the other hand, we connect upper bounds of rank(S) to upper bounds of ν(S) (ν_d(S)).

KEYWORDS:

• Cayley digraphs of monoids
• endomorphism monoids of graphs

2010 Mathematics Subject Classification:

• Primary: 05C25
• Secondary: 05C20

Acknowledgment

The author expresses his gratitude to the referee for valuable suggestions, which improved the manuscript.