# zbMATH — the first resource for mathematics

Directed graphs and combinatorial properties of semigroups. (English) Zbl 1005.20043
Let $$D$$ be a fixed finite graph. The graph $$G=(V,E)$$ is said to be $$D$$-saturated if for every infinite subset $$W$$ of $$V$$ there exists a subgraph of $$G$$ isomorphic with $$D$$ having all vertices in $$W$$.
Let $$S$$ be a semigroup. The authors associate to $$S$$ the following three graphs: $$\text{Pow}(S)$$, $$\text{Div}(S)$$, $$\text{Ann}(S)$$ for which $$S$$ is the vertex set (in the construction of $$\text{Div}(S)$$ $$S$$ is assumed to be a semigroup with $$0$$). The set of edges is defined as follows. If $$u,v\in S$$ and $$u\neq v$$ then:
$$(u,v)$$ is a edge for $$\text{Pow}(s)\iff v$$ is a power of $$u$$.
$$(u,v)$$ is a edge for $$\text{Div}(S)\iff u$$ divides $$v$$,
$$(u,v)$$ is a edge for $$\text{Ann}(S)\iff uv=0$$.
The purpose of this paper is to characterize the commutative semigroups $$S$$ for which the graphs $$\text{Pow}(S)$$ or $$\text{Div}(S)$$ or $$\text{Ann}(S)$$ are $$D$$-saturated.

##### MSC:
 20M14 Commutative semigroups 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C20 Directed graphs (digraphs), tournaments 20M05 Free semigroups, generators and relations, word problems
Full Text:
##### References:
 [1] Chartland, G.; Lesniak, L., Graphs and digraphs, (1996), Chapman & Hall London [2] Clifford, A.H.; Preston, G.B., The algebraic theory of semigroups, (1961), Amer. Math. Soc Providence · Zbl 0111.03403 [3] de Luca, A.; Varricchio, S., Regularity and finiteness conditions, (), 747-810 [4] de Luca, A.; Varricchio, S., Finiteness and regularity in semigroups and formal languages, Monographs in theoretical computer science, (1998), Springer-Verlag Berlin [5] Graham, R.L., Rudiments of Ramsey theory, (1981), Amer. Math. Soc Providence [6] Graham, R.L.; Rothschild, B.L.; Spencer, J.H., Ramsey theory, Discrete math. and optimization, (1990), Wiley New York [7] Grillet, P.A., Semigroups: an introduction to structure theory, (1995), Dekker New York · Zbl 0874.20039 [8] Howie, J.M., Fundamentals of semigroup theory, (1995), Clarendon Press Oxford · Zbl 0835.20077 [9] Justin, J., Characterisation of the repetitive commutative semigroups, J. algebra, 21, 87-90, (1972) · Zbl 0248.05004 [10] Justin, J.; Kelarev, A.V., Factorisations of infinite sequences in semigroups, Ann. mat. pura appl., 174, 87-96, (1998) · Zbl 0963.20034 [11] Kelarev, A.V., Combinatorial properties of sequences in groups and semigroups, Combinatorics, complexity and logic, Discrete mathematics and theoretical computer science, (1996), Springer-Verlag Auckland, p. 289-298 · Zbl 0914.68155 [12] Lothaire, M., Combinatorics on words, (1983), Addison-Wesley London · Zbl 0514.20045 [13] Robinson, D.J.S., A course in the theory of groups, (1982), Springer-Verlag New York/Berlin · Zbl 0496.20038 [14] Shevrin, L.N.; Ovsyannikov, A.J., Semigroups and their subsemigroup lattices, (1996), Kluwer Academic Dordrecht · Zbl 0858.20054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.