共查询到20条相似文献，搜索用时 11 毫秒
1.
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 . 相似文献
2.
AN APPROACH TO CONSTRUCT AN END-REGULAR GRAPH 总被引：1，自引：0，他引：1
LIWEIMIN 《高校应用数学学报(英文版)》1998,13(2):171-178
In this paper,an approach to construct a nontrivial end-regular graph of any order under some conditions are given. 相似文献
3.
称图X是End-正则图如果它的自同态幺半解EndX是正则的幺半解，即关于任意自同态f存在一个自同态g使得fgf=f。本文对顶点度数小于4的End-正则循环图进行了刻划。 相似文献
4.
Suohai Fan 《Discrete Mathematics》2002,257(1):161-164
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. 相似文献
5.
Let be a lattice with and . An endomorphism of is a -endomorphism, if it satisfies and . The -endomorphisms of form a monoid. In 1970, the authors proved that every monoid can be represented as the -endomorphism monoid of a suitable lattice with and . In this paper, we prove the stronger result that the lattice with a given -endomorphism monoid can be constructed as a uniquely complemented lattice; moreover, if is finite, then can be chosen as a finite complemented lattice.
6.
Emil Daniel Schwab 《Algebra Colloquium》2020,(2):181-192
The paper introduces a class of inverse (sub)monoids which contains Jones-Lawson's gauge inverse (sub)monoid.The aim is to give examples and the basic propertie... 相似文献
7.
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))m2. 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 相似文献
8.
9.
James East 《代数通讯》2013,41(5):1671-1689
We give a semigroup presentation of the singular part of the symmetric inverse monoid on a finite set. Along the way, we derive a monoid presentation of the monoid of all order-preserving injective partial transformations on a finite chain, which differs from the presentation discovered by Fernandes. 相似文献
10.
Roland Kaschek 《Discrete Mathematics》2010,310(8):1275-1281
This paper proves a necessary and sufficient condition for the endomorphism monoid of a lexicographic product G[H] of graphs G,H to be the wreath product of the monoids and . The paper also gives respective necessary and sufficient conditions for specialized cases such as for unretractive or triangle-free graphs G. 相似文献
11.
51.IntroductionandPreIiminariesThemonoidofendomorphismsofagraph,inparticular,thatofstrongendomorphismsofagraph,hasbeentheobjectofresearchesinthetheoryofsemigroupsforquitesometime(cf.Llj-Lloj).LlJandL2jcanserveasasurvey.Theaimoftheseresearchesistocon-tributetothealgebraicanalysisofgraphs.Thesubjectyieldssomeinterestsincetheresultsoftheseresearchesmayopenvastpossibilitiesforapplicationsofsemigrouptheorytographtheo-ry.InL1]andL3j,ithasbeenprovedthatforfinitegraphG,sEnd(G),themonoidofstrongen… 相似文献
12.
A graph G is called a pseudo-core if every endomorphism of G is either an automorphism or a colouring. A graph G is a core if every endomorphism of G is an automorphism. Let be the finite field with q elements where q is a power of an odd prime number. The quadratic forms graph, denoted by where , has all quadratic forms on as vertices and two vertices f and g are adjacent whenever or 2. We prove that every is a pseudo-core. Further, when n is even, is a core. When n is odd, is not a core. On the other hand, we completely determine the independence number of . 相似文献
14.
15.
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. 相似文献
16.
The present paper proves necessary and sufficient conditions for both lexicographic products and arbitrary graphs to be unretractive. The paper also proves that the automorphism group of a lexicographic product of graphs is isomorphic to a wreath product of a monoid with a small category. 相似文献
17.
Jim Coykendall 《代数通讯》2017,45(7):2795-2808
In this note, we investigate ideal and factorization-theoretic properties of some root closed cancellative commutative monoids of rank at most two. 相似文献
18.
Ｔｈｅｍｏｎｏｉｄｏｆｅｎｄｏｍｏｒｐｈｉｓｍｓｏｆａｇｒａｐｈ ,ｉｎｐａｒｔｉｃｕｌａｒ,ｔｈａｔｏｆｓｔｒｏｎｇｅｎｄｏｍｏｒｐｈｉｓｍｓｏｆａｇｒａｐｈ ,ｈａｓｂｅｅｎｔｈｅｏｂｊｅｃｔｏｆｒｅｓｅａｒｃｈｅｓｉｎｔｈｅｔｈｅｏｒｙｏｆｓｅｍｉｇｒｏｕｐｓｆｏｒｑｕｉｔｅｓｏｍｅｔｉｍｅ(ｃｆ .[1 ]— [9]) .Ａｓｉｓｐｏｉｎｔｅｄｏｕｔｉｎｓｏｍｅｓｔａｎｄａｒｄｂｏｏｋｓｏｎｓｅｍｉｇｒｏｕｐｔｈｅｏｒｙｓｕｃｈａｓ[1 0 ],ｔｈｅｉｄｅａｏｆｄｅｄｕｃｉｎｇｆａｃｔｓａｂｏｕｔｔｈｅｓｅｍｉ… 相似文献
19.
图的字典序积和自同态幺半群 总被引：3，自引：1，他引：3
Ｆ．Ｈａｒａｒｙ￣［１］和Ｇ．Ｓａｂｉｄｕｓｓｉ￣［２］考虑过图Ｘ和ｙ的字典序积Ｘ［Ｙ］的自同构群ＡｕｔＸ［Ｙ］与它们各自的自同构群的圈积ＡｕｔＸ［ＡｕｔＹ］的关系,并给出了两者相等的一种刻划．在本文,我们考虑更广意义上的问题,即Ｘ［Ｙ］的自同态幺半群ＥｎｄＸ［Ｙ］与各自的自同态幺半群的圈积ＥｎｄＸ［ＥｎｄＹ］的关系,也给出了两者相等的一种刻划,同时得到了下面结果：如果Ｘ和Ｙ都是不含Ｋ＿３导出子图的连通图,且其中之一图有奇数围长,那么ＥｎｄＸ［Ｙ］＝ＥｎｄＸ［ＥｎｄＹ］． 相似文献
20.
The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K3‐free and K4‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000 相似文献