共查询到20条相似文献,搜索用时 0 毫秒
1.
Symmetry of graphs has been extensively studied over the past fifty years by using automorphisms of graphs and group theory which have played and still play an important role for graph theory, and promising and interesting results have been obtained, see for examples, [L.W. Beineke, R.J. Wilson, Topics in Algebraic Graph Theory, Cambridge University Press, London, 2004; N. Biggs, Algebraic Graph Theory, Cambridge University Press, London, 1993; C. Godsil, C. Royle, Algebraic graph theory, Springer-Verlag, London, 2001; G. Hahn, G. Sabidussi, Graph Symmetry: Algebraic Methods and Application, in: NATO ASI Series C, vol. 497, Kluwer Academic Publishers, Dordrecht, 1997]. We introduced generalized symmetry of graphs and investigated it by using endomorphisms of graphs and semigroup theory. In this paper, we will survey some results we have achieved in recent years. The paper consists of the following sections.
- 1. Introduction
- 2. End-regular graphs
- 3. End-transitive graphs
- 4. Unretractive graphs
- 5. Graphs and their endomorphism monoids.
Keywords: Graph; Endomorphism; Monoid; Generalized symmetry; End-regular; End-transitive; Unretractive 相似文献
2.
3.
4.
We answer some questions about the existence of graphs with a given endotype posed in Böttcher and Knauer (Discrete Math. 109 (1992) 45–57). All definitions and needed terminology can be found there and for brevity they will not be repeated here. All results have been obtained by computer calculations. 相似文献
5.
强自同态半群构成并群的图族 总被引:1,自引:0,他引:1
李为民 《数学物理学报(A辑)》2006,26(4):570-577
该文给出强自同态半群构成并群的图族的特征, 同时文中也明确刻划了其中每个群的单位元. 相似文献
6.
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. 相似文献
7.
8.
Yan Zhibin 《东北数学》1998,(2)
SomeNotesaboutTanaka'sEquationYanZhibin(严质彬)(DepartmentofMathematics,HarbinInstituteofTechnology,Harbin,150001)AbstractLet{Wt... 相似文献
9.
《Discrete Mathematics》2022,345(3):112713
In this note we give an example of a reflexive digraph that has no non-trivial retractions, but does have non-trivial endomorphisms. 相似文献
10.
李为民 《数学物理学报(B辑英文版)》1997,(4)
1IntroductionConsiderableattelltionhasbeendevotedtotilesemigroupoftheelldomorphislllsofagraph,inparticular,thesemigroupofthestrongendomorpllisnasofagraph,seesurvey[1].Themainpurposeoftheseresearchesliesintheapplicatiollsofthealgebraictheoryofsendgroupstothetheoryofgraphs.ItiswellknowllthatoneofthemostimportantconceptsillselltigrouptheoryisGreen'srelations.In[2],thecharacterizatiollofGreen'srelationsonsEnd(G),themolloidofthestrongendomorphisnisofagrapllG.isgiven.LetSbeasemigroup.Thenotation… 相似文献
11.
Weimin Li 《Discrete Mathematics》2005,300(1-3):245-255
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. 相似文献
12.
13.
△(G)≤4的外平面图的邻强边色数 总被引:3,自引:0,他引:3
研究了△(G)≤4的外平面图的强边染色,证明了△(G)≤X′as(G)≤△(G)+1,且X′as(G)=△(G)+1当且仅当存在两具最大度点相邻,其中△(G)和X′as(G)分别表示图G的最大度和邻强边色数,并且提出了如下猜想:如果G是一个|V(G)|≥3(G≠C5)的2-连通图,则△(G)≤X′as(G)≤△(G)+2。 相似文献
14.
Weimin Li 《数学学报(英文版)》1995,11(4):372-380
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. 相似文献
15.
Toru Kojima 《Discrete Mathematics》2008,308(7):1282-1295
The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)-f(y)|:xy∈E(G)} taken over all proper numberings f of G. The strong product of two graphs G and H, written as G(SP)H, is the graph with vertex set V(G)×V(H) and with (u1,v1) adjacent to (u2,v2) if one of the following holds: (a) u1 and v1 are adjacent to u2 and v2 in G and H, respectively, (b) u1 is adjacent to u2 in G and v1=v2, or (c) u1=u2 and v1 is adjacent to v2 in H. In this paper, we investigate the bandwidth of the strong product of two connected graphs. Let G be a connected graph. We denote the diameter of G by D(G). Let d be a positive integer and let x,y be two vertices of G. Let denote the set of vertices v so that the distance between x and v in G is at most d. We define δd(G) as the minimum value of over all vertices x of G. Let denote the set of vertices z such that the distance between x and z in G is at most d-1 and z is adjacent to y. We denote the larger of and by . We define η(G)=1 if G is complete and η(G) as the minimum of over all pair of vertices x,y of G otherwise. Let G and H be two connected graphs. Among other results, we prove that if δD(H)(G)?B(G)D(H)+1 and B(H)=⌈(|V(H)|+η(H)-2)/D(H)⌉, then B(G(SP)H)=B(G)|V(H)|+B(H). Moreover, we show that this result determines the bandwidth of the strong product of some classes of graphs. Furthermore, we study the bandwidth of the strong product of power of paths with complete bipartite graphs. 相似文献
16.
C. A. Carvalho 《代数通讯》2013,41(8):2871-2886
We first consider the class of monoids in which every left invertible element is also right invertible, and prove that if a monoid belonging to this class admits a finitely presented Bruck–Reilly extension then it is finitely generated. This allow us to obtain necessary and sufficient conditions for the Bruck–Reilly extensions of this class of monoids to be finitely presented. We then prove that thes 𝒟-classes of a Bruck–Reilly extension of a Clifford monoid are Bruck–Reilly extensions of groups. This yields another necessary and sufficient condition for these Bruck–Reilly extensions to be finitely generated and presented. Finally, we show that a Bruck–Reilly extension of a Clifford monoid is finitely presented as an inverse monoid if and only if it is finitely presented as a monoid, and that this property cannot be generalized to Bruck–Reilly extensions of arbitrary inverse monoids. 相似文献
17.
Mary E. Hopkins 《代数通讯》2013,41(11):4333-4347
An integral domain D is weakly integrally closed if whenever x is in the quotient field of D, and J is a nonzero finitely generated ideal of D such that xJ ? J 2, then x is in D. We define weakly integrally closed (WIC) numerical monoids similarly. If a monoid algebra is weakly integrally closed, then so is the monoid. The characteristic function of a numerical monoid M can be thought of as an infinite binary string s(M). A pattern of finitely many 0's and 1's is called forbidden if whenever s(M) contains it, then M is not weakly integrally closed. The pattern 11011 is forbidden. We show that a numerical monoid M is WIC if and only if s(M) contains no forbidden patterns. We also show that for every finite set S of forbidden patterns, there exists a numerical monoid M that is not WIC and for which s(M) contains no stretch (in a natural sense) of a pattern in S. 相似文献
18.
A generalization of strong regularity around a vertex subset C of a graph γ , which makes sense even if γ is non-regular, is studied. Such a structure appears, together with a kind of distance-regularity around C , when an spectral bound concerning the so-called predistance polynomial of C is attained. As a main consequence of these results, it is shown that a regular (connected) graph γ with d + 1 distinct eigenvalues is distance-regular, and its distance- d graph γ d is strongly regular with parameters a = c , if and only if the number of vertices at distance d from each vertex satisfies an expression which depends only on the order of γ and the different eigenvalues of γ . 相似文献
19.
A generalization of strong regularity around a vertex subset C of a graph Γ, which makes sense even if Γis non-regular, is studied. Such a structure appears, together with a kind of distance-regularity around C , when an spectral bound concerning the so-called predistance polynomial of C is attained. As a main consequence of these results, it is shown that a regular (connected) graph Γwith d + 1 distinct eigenvalues is distance-regular, and its distance- d graph Γ d is strongly regular with parameters a = c , if and only if the number of vertices at distance d from each vertex satisfies an expression which depends only on the order of Γand the different eigenvalues of Γ. 相似文献
20.
The main goal of this paper is to define Gröbner–Shirshov bases for some monoids. Therefore, after giving some preliminary material, we first give Gröbner–Shirshov bases for graphs and Schützenberger products of monoids in separate sections. In the final section, we further present a Gröbner–Shirshov basis for a Rees matrix semigroup. 相似文献