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 .     

Absolute graphs with prescribed endomorphism monoid

We consider endomorphism monoids of graphs. It is well-known that any monoid can be represented as the endomorphism monoid M of some graph Γ with countably many colors. We give a new proof of this theorem such that the isomorphism between the endomorphism monoid $\mathop{\rm End}\nolimits (\Gamma)We consider endomorphism monoids of graphs. It is well-known that any monoid can be represented as the endomorphism monoid M of some graph Γ with countably many colors. We give a new proof of this theorem such that the isomorphism between the endomorphism monoid and M is absolute, i.e. holds in any generic extension of the given universe of set theory. This is true if and only if |M|,|Γ| are smaller than the first Erdős cardinal (which is known to be strongly inaccessible). We will encode Shelah’s absolutely rigid family of trees (Isr. J. Math. 42(3), 177–226, 1982) into Γ. The main result will be used to construct fields with prescribed absolute endomorphism monoids, see G?bel and Pokutta (Shelah’s absolutely rigid trees and absolutely rigid fields, in preparation). This work was supported by the project No. I-706-54.6/2001 of the German-Israeli Foundation for Scientific Research & Development and a fellowship within the Postdoc-Programme of the German Academic Exchange Service (DAAD).     

The join of split graphs whose half-strong endomorphisms form a monoid

In this paper, the half-strong endomorphisms of the join of split graphs are investigated. We give the conditions under which the half-strong endomorphisms of the join of split graphs form a monoid.     

Split graphs whose half-strong endomorphisms form a monoid

In this paper,the half-strong,the locally strong and the quasi-strong endomorphisms of a split graph are investigated.Let X be a split graph and let End(X),hEnd(X),lEnd(X) and qEnd(X) be the endomorphism monoid,the set of all half-strong endomorphisms,the set of all locally strong endomorphisms and the set of all quasi-strong endomorphisms of X,respectively.The conditions under which hEnd(X) forms a submonoid of End(X) are given.It is shown that lEnd(X) = qEnd(X) for any split graph X.The conditions under which lEnd(X)(resp.qEnd(X)) forms a submonoid of End(X) are also given.In particular,if hEnd(X) forms a monoid,then lEnd(X)(resp.qEnd(X)) forms a monoid too.     

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.

     

广义字典序积的自同态幺半群

讨论了图的广义字典序积的自同态幺半群的性质,给出了广义字典序积图X[Yz|x∈V（X）]的自同态幺半群与X,Yx(x∈V(X))的自同态幺半群的圈积相等的充要条件。     

On Primitive Idempotents of the Strong Endomorphism Monoid of a Graph

51.IntroductionandPreIiminariesThemonoidofendomorphismsofagraph,inparticular,thatofstrongendomorphismsofagraph,hasbeentheobjectofresearchesinthetheoryofsemigroupsforquitesometime(cf.Llj-Lloj).LlJandL2jcanserveasasurvey.Theaimoftheseresearchesistocon-tributetothealgebraicanalysisofgraphs.Thesubjectyieldssomeinterestsincetheresultsoftheseresearchesmayopenvastpossibilitiesforapplicationsofsemigrouptheorytographtheo-ry.InL1]andL3j,ithasbeenprovedthatforfinitegraphG,sEnd(G),themonoidofstrongen…     

On graphs with given main eigenvalues

An eigenvalue of a graph is main if it has an eigenvector, the sum of whose entries is not equal to zero. Extending previous results of Hagos and Hou et al. we obtain two conditions for graphs with given main eigenvalues. All trees and connected unicyclic graphs with exactly two main eigenvalues were characterized by Hou et al. Extending their results, we determine all bicyclic connected graphs with exactly two main eigenvalues.     

二部图的E-H-不可收缩性

By End（G） and hEnd（G） we denote the set of endomorphisms and half-strong endomorphisms of a graph G respectively. A graph G is said to be E-H-unretractive if End（G） = hEnd（G）. A general characterization of an E-H-unretractive graph seems to be difficult. In this paper, bipartite graphs with E-H-unretractivity are characterized explicitly.     

On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.     

INVERSE MONOIDS OF GRAPHS

. IntroductionGraph endomorphism and its regularity property have been investigated in some literatures (of. [1--41 for examples). The invertibility is a stronger algebraic property thanregUlarity in semigroup theory. It is commonly agreed that inverse semigroups are the mostpromising class of semigroups for study. In this paper we first present a combinatorial characterization of an inverse monoid of a graph (Theorem 2.3). Then using this we prove thata bipartite graph with an inverse monoi…     

The Covering Relation of Idempotents in the Strong Endomorphism Monoid of a Graph

Ｔｈｅｍｏｎｏｉｄｏｆｅｎｄｏｍｏｒｐｈｉｓｍｓｏｆａｇｒａｐｈ ,ｉｎｐａｒｔｉｃｕｌａｒ,ｔｈａｔｏｆｓｔｒｏｎｇｅｎｄｏｍｏｒｐｈｉｓｍｓｏｆａｇｒａｐｈ ,ｈａｓｂｅｅｎｔｈｅｏｂｊｅｃｔｏｆｒｅｓｅａｒｃｈｅｓｉｎｔｈｅｔｈｅｏｒｙｏｆｓｅｍｉｇｒｏｕｐｓｆｏｒｑｕｉｔｅｓｏｍｅｔｉｍｅ(ｃｆ .[1 ]— [9]) .Ａｓｉｓｐｏｉｎｔｅｄｏｕｔｉｎｓｏｍｅｓｔａｎｄａｒｄｂｏｏｋｓｏｎｓｅｍｉｇｒｏｕｐｔｈｅｏｒｙｓｕｃｈａｓ[1 0 ],ｔｈｅｉｄｅａｏｆｄｅｄｕｃｉｎｇｆａｃｔｓａｂｏｕｔｔｈｅｓｅｍｉ…     

On the spectral spread of bicyclic graphs with given girth

The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and |E(G)| = |V(G)|+ 1. Let B(n, g) be the set of bicyclic graphs on n vertices with girth g. In this paper some properties about the least eigenvalues of graphs are given, by which the unique graph with maximal spectral spread in B(n, g) is determined.     

Retractions of split graphs and End-orthodox split graphs

A retraction f of a graph G is an edge-preserving mapping of G with f(v)=v for all v∈V(H), where H is the subgraph induced by the range of f. A graph G is called End-orthodox (End-regular) if its endomorphism monoid End X is orthodox (regular) in the semigroup sense. It is known that a graph is End-orthodox if it is End-regular and the composition of any two retractions is also a retraction. The retractions of split graphs are given and End-orthodox split graphs are characterized.     

图的P-正则自同态幺半群

刻划了具有Ｐ－正则自同态幺半群的二分图,讨论了字典序积图的自同态幺半群的Ｐ－正则性。