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.     

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     

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).     

图的强收缩核与图的强自同态幺半群的正则性

本文研究图及其强自同态幺半群．首先刻画了图的强自同态幺半群的正则元，然后给出了此幺半群正则的充要条件．这推广了［１］和［２］中关于有限图的强自同态幺半群正则的结果．     

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.

     

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 .     

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…     

具有完全正则自同态半群的分裂图

本文给出了具有完全正则自同态半群的分裂图的结构特征．其证明方法有望应用于其他图族自同态半群的正则性及完全正则性的研究．     

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

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

The Join of Split Graphs Whose Regular Endomorphisms Form a Monoid

In this paper, the regular endomorphisms of the join of split graphs are investigated. We give a condition under which the regular endomorphisms of the join of split graphs form a monoid.     

Split and balanced colorings of complete graphs

An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain K_n in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph K_N has a coloring which is not (r, n)-split is denoted by ƒ_r(n). Balanced (r,n)-colorings are defined as edge r-colorings of KN such that every subset of [N/r] vertices contains a monochromatic K_n in all colors. Then g_r(n) is defined as the smallest N such that K_N has a balanced (r, n)-coloring. The definitions imply that f_r(n) g_r(n). The paper gives estimates and exact values of these functions for various choices of parameters.     

Strong Convergence of a Split Common Fixed Point Problem

In this article, we present a new general algorithm for solving the split common fixed point problem in an infinite dimensional Hilbert space, which is to find a point which belongs to the common fixed point of a family of quasi-nonexpansive mappings such that its image under a linear transformation belongs to the common fixed point of another family of quasi-nonexpansive mappings in the image space. We establish the strong convergence for the algorithm to find a unique solution of the variational inequality, which is the optimality condition for the minimization problem. The algorithm and its convergence results improve and develop previous results in this field.     

图的不可收缩性和end-正则性

图的半群理论是图的群理论的延伸．图的不可收缩性和end－正则性是其中受到普遍关注的课题．本文揭示了两者之间的内在联系．     

Split non-threshold Laplacian integral graphs

The aim of this article is to answer a question posed by Merris in European Journal of Combinatorics, 24 (2003) pp. 413 ? 430, about the possibility of finding split non-threshold graphs that are Laplacian integral, i.e. graphs for which the eigenvalues of the corresponding Laplacian matrix are integers. Using Kronecker products, balanced incomplete block designs, and solutions to certain Diophantine equations, we show how to build infinite families of these graphs.     

Locally s‐distance transitive graphs

We give a unified approach to analyzing, for each positive integer s, a class of finite connected graphs that contains all the distance transitive graphs as well as the locally s‐arc transitive graphs of diameter at least s. A graph is in the class if it is connected and if, for each vertex v, the subgroup of automorphisms fixing v acts transitively on the set of vertices at distance i from v, for each i from 1 to s. We prove that this class is closed under forming normal quotients. Several graphs in the class are designated as degenerate, and a nondegenerate graph in the class is called basic if all its nontrivial normal quotients are degenerate. We prove that, for s≥2, a nondegenerate, nonbasic graph in the class is either a complete multipartite graph or a normal cover of a basic graph. We prove further that, apart from the complete bipartite graphs, each basic graph admits a faithful quasiprimitive action on each of its (1 or 2) vertex‐orbits or a biquasiprimitive action. These results invite detailed additional analysis of the basic graphs using the theory of quasiprimitive permutation groups. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:176‐197, 2012     

Constructing cospectral graphs via a new form of graph product

We present a new method to construct a family of co-spectral graphs. Our method is based on a new type of graph product that we define, the bipartite graph product, which may be of self-interest. Our method is different from existing techniques in the sense that it is not based on a sequence of local graph operations (e.g. Godsil–McKay switching). The explicit nature of our construction allows us, for example, to construct an infinite family of cospectral graphs and provide an easy proof of non-isomorphism. We are also able to characterize fully the spectrum of the cospectral graphs.     

图的正则强自态的逆

本文从组合角度明确刻画了图的完全正则强自同态的交换伪逆，同时给出它们的计数公式．