The monoid of strong endomorphisms of a graph

We explicitly find all the idempotents in eachL(R)-class and all the inverses of each element of the strong endomorphism monoid of a graph. The number of these idempotents and inverses is also obtained. The author is deeply indebted to Professor Dr. T. E. Hall for his stimulating questions about this theme and much improvement made to an earlier version of this paper. The author would like to thank Professor Dr. U. Knauer and Dr. E. Wilkeit for helpful comments.     

Various inverses of a strong endomorphism of a graph

In this paper, we first give a characterization of a completely regular strong endomorphism of a graph. Then we explicitly exhibit its various inverses. The enumerations of them are also derived.     

Inverses and pseudo-inverses of a strong endomorphism of a graph

In this paper, we explicitly describe all the inverses and pseudo-inverses of a strong endomorphism of a graph. The number of them is determined. In addition, we give a characterization of a strong endomorphism whose pseudo-inverse set coincides with its inverse set. The graph, each strong endomorphism of which has this property, is also investigated.     

On graphs with a given endomorphism monoid

Hedrlín and Pultr proved that for any monoid M there exists a graph G with endomorphism monoid isomorphic to M . In this paper we give a construction G(M) for a graph with prescribed endomorphism monoid M . Using this construction we derive bounds on the minimum number of vertices and edges required to produce a graph with a given endomorphism monoid for various classes of finite monoids. For example we show that for every monoid M , | M |=m there is a graph G with End(G)? M and |E(G)|≤(1 + 0(1))m². This is, up to a factor of 1/2, best possible since there are monoids requiring a graph with \begin{eqnarray*} && \frac{m^{2}}{2}(1 -0(1)) \end{eqnarray*} edges. We state bounds for the class of all monoids as well as for certain subclasses—groups, k‐cancellative monoids, commutative 3‐nilpotent monoids, rectangular groups and completely simple monoids. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 241–262, 2009     

On the number of graphs with a given endomorphism monoid

For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then .     

The rank of the endomorphism monoid of a uniform partition

The rank of a semigroup is the cardinality of a smallest generating set. In this paper we compute the rank of the endomorphism monoid of a non-trivial uniform partition of a finite set, that is, the semigroup of those transformations of a finite set that leave a non-trivial uniform partition invariant. That involves proving that the rank of a wreath product of two symmetric groups is two and then use the fact that the endomorphism monoid of a partition is isomorphic to a wreath product of two full transformation semigroups. The calculation of the rank of these semigroups solves an open question.     

Automorphisms of the endomorphism semigroup of a free monoid or a free semigroup

We determine all isomorphisms between the endomorphism semigroups of free monoids or free semigroups and prove that automorphisms of the endomorphism semigroup of a free monoid or a free semigroup are inner or ``mirror inner". In particular, we answer a question of B. I. Plotkin.

     

The endomorphism monoid of a free trioid of rank 1

We describe all endomorphisms of a free trioid of rank 1 and construct a semigroup which is isomorphic to the endomorphism monoid of such free trioid. Also, we give an abstract characteristic for the endomorphism monoid of a free trioid of rank 1 and prove that free trioids are determined by their endomorphism monoids.     

Semilattices with the strong endomorphism kernel property

An endomorphism on an algebra ${\mathcal{A}}$ is said to be strong if it is compatible with every congruence on ${\mathcal{A}}$ , and ${\mathcal{A}}$ is said to have the strong endomorphism kernel property provided every congruence on ${\mathcal{A}}$ , other than the universal congruence, is the kernel of a strong endomorphism on ${\mathcal{A}}$ . In this note, we characterize those semilattices that have this property.     

一类广义变换半群的格林关系

设X是一个全序集,E是X上的一个凸等价关系．令 OE（X）={f∈TE（X）：Ax,y∈X,x≤y→f（x）≤f（y））, 其中TE（X）是E-保持变换半群．对于取定的θ∈OE（X）,在OE（X）上定义运算fog=fθg,使OE（X）成为广义半群OE（X;θ）．对于有限全序集X上的凸等价关系E,本文刻画了广义半群OE（X;θ）的正则元,描述了这个半群的格林关系．     

关于一类半环上的格林关系的若干研究

研究了加法半群是带,乘法半群是完全正则半群的半环上的格林关系,给出了˙L∧+D(+L,+R)是同余关系的充分必要条件,证明了由这些同余关系所决定的半环类都是半环簇,并给出了这些半环簇的Mal′cev积分解.     

The strong chromatic number of a graph

It is shown that there is an absolute constant c with the following property: For any two graphs G₁ = (V, E₁) and G₂ = (V, E₂) on the same set of vertices, where G₁ has maximum degree at most d and G₂ is a vertex disjoint union of cliques of size cd each, the chromatic number of the graph G = (V, E₁ U E₂) is precisely cd. The proof is based on probabilistic arguments.     

All countable monoids embed into the monoid of the infinite random graph

We prove that the full transformation monoid on a countably infinite set is isomorphic to a submonoid of , the endomorphism monoid of the infinite random graph R. Consequently, embeds each countable monoid, satisfies no nontrivial monoid identity, and has an undecidable universal theory.     

Endomorphisms of graphs I. The monoid of strong endomorphisms

Wit danken Elke Wilkeit und Michael Boettcher für viele Anregungen zum Thema dieser Arbeit.