关于图的自同态的若干研究
|
摘要
图的自同构将图与群联系起来,这成为图论研究中一种重要的方法.图的自同态把图与半群联系起来,并将半群理论的研究应用于图论的研究,从而建立起图论与半群理论之间的联系.图的自同态么半群和图的正则性以及图的自同态么半群的格林关系引起了广大图论学者和半群学者的极大兴趣,如李为民在[16]中给出了一个图的强自同态么半群上的格林关系;1988年Marki在[21]中提出了公开问题:哪类图的自同态幺半群是正则的?M.Bottcher和U.Knauer在[5]中引入并研究了图的自同态谱和自同态型,并提出了如下公开问题:在什么条件下,图的半强自同态(局部强自同态、拟强自同态)成为么半群?然而对以上问题要给出一个普遍的回答是十分困难的.因此解决这些问题的途径是对于具体的图进行具体研究。
本文以n-棱柱和分裂图及分裂图的连图为研究对象,针对上述问题展开研究工作。首先刻画了n为奇数时n-棱柱自同态,并证明了它的自同态幺半群是正则的,通过幺半群上的格林关系的研究,给出了它的D-结构,完全确定了这类图的自同态谱与型。并证明了n为偶数时n-棱柱的拟强自同态构成幺半群,完全确定了这类图的自同态型。其次,通过对格林关系的研究,确定了自同态正则分裂图的自同态幺半群的一些计数问题。最后以分裂图的连图为研究对象,刻画两个分裂图的连图的局部强自同态,并证明了每个局部强自同态都是拟强的,给出了两个分裂图的连图的所有局部强自同态构成么半群的条件。
The autmorphisms of graph connects group with graph theory,and becomes an important and effect way in the studying of the graph theory.Generalizing the way,the endomorphisms of graph tries to establish the relationship between graph theory and algebra theory of semigroup and to apply the theory of semigroups to graph theory.Many authors pay much attention to endomorphism monoids of graphs,regularities of graphs and Green's equivalences of endomorphism monoids.Such as Weimin Li gives a Green's equivalences of strong-endomorphisms in[16].Maeki posed a open question in[21]:the endomorphisms monoids of which graphs are regular? Moreover,M.Bottcher and U.Knauer in[5]introduced the endomorphism spectrum and the endomorphism type of a graph,and the following question was posed:For a graph X, under which conditions do the sets hEndX,1EndX,qEndX form monoids? However,it seems difficult to obtain a general answer to the above questions.So the strategy for solving these questions are finding various kinds of conditions for various kinds of graphs.
In the paper,for the above question,we mainly take the n-prism,the split graph and the join of two split graphs as investigative objects and investigate some problems on the bases of these.Firstly,we character the endomorphisms of the n-prism prove that it is regular. Consequently,we give D Green's equivalences of it.Moreover,we character the quasi-strong endomorphisms of the n-prism when n is even and m≥2 and it was proved that it is not regular and the quasi-strong endomorphisms of n-prism forms monoids.At the same time, the corresponding endomorphism spectrum and the endomorphism type of the kind of graph were given.Secondly,we discuss the number of idempotent and the image of endomorphism of the End-regular split graphs.Accordingly,the number of L class and R class was given. At last,we character the local-strong endomorphisms of the join of two split graphs and prove that quasi-strong endomorphisms of it is local-strong.And we give a condition under which the join of two split graphs forms monoids.
本文以n-棱柱和分裂图及分裂图的连图为研究对象,针对上述问题展开研究工作。首先刻画了n为奇数时n-棱柱自同态,并证明了它的自同态幺半群是正则的,通过幺半群上的格林关系的研究,给出了它的D-结构,完全确定了这类图的自同态谱与型。并证明了n为偶数时n-棱柱的拟强自同态构成幺半群,完全确定了这类图的自同态型。其次,通过对格林关系的研究,确定了自同态正则分裂图的自同态幺半群的一些计数问题。最后以分裂图的连图为研究对象,刻画两个分裂图的连图的局部强自同态,并证明了每个局部强自同态都是拟强的,给出了两个分裂图的连图的所有局部强自同态构成么半群的条件。
The autmorphisms of graph connects group with graph theory,and becomes an important and effect way in the studying of the graph theory.Generalizing the way,the endomorphisms of graph tries to establish the relationship between graph theory and algebra theory of semigroup and to apply the theory of semigroups to graph theory.Many authors pay much attention to endomorphism monoids of graphs,regularities of graphs and Green's equivalences of endomorphism monoids.Such as Weimin Li gives a Green's equivalences of strong-endomorphisms in[16].Maeki posed a open question in[21]:the endomorphisms monoids of which graphs are regular? Moreover,M.Bottcher and U.Knauer in[5]introduced the endomorphism spectrum and the endomorphism type of a graph,and the following question was posed:For a graph X, under which conditions do the sets hEndX,1EndX,qEndX form monoids? However,it seems difficult to obtain a general answer to the above questions.So the strategy for solving these questions are finding various kinds of conditions for various kinds of graphs.
In the paper,for the above question,we mainly take the n-prism,the split graph and the join of two split graphs as investigative objects and investigate some problems on the bases of these.Firstly,we character the endomorphisms of the n-prism prove that it is regular. Consequently,we give D Green's equivalences of it.Moreover,we character the quasi-strong endomorphisms of the n-prism when n is even and m≥2 and it was proved that it is not regular and the quasi-strong endomorphisms of n-prism forms monoids.At the same time, the corresponding endomorphism spectrum and the endomorphism type of the kind of graph were given.Secondly,we discuss the number of idempotent and the image of endomorphism of the End-regular split graphs.Accordingly,the number of L class and R class was given. At last,we character the local-strong endomorphisms of the join of two split graphs and prove that quasi-strong endomorphisms of it is local-strong.And we give a condition under which the join of two split graphs forms monoids.
引文
[1]C.Godsil and G.Royle,Algebraic Graph Theory,Springer Verlag,London,(2001).
[2]F.Harary,Graph Theory,Addison-Wesley Reading,(1969).
[3]J.M.Howie,Fundamentals of Semigroup Theory,Clarandon Press,(1995).
[4]Thomas W.Hungerford,Algebra,Springer Verlag,London,(1974).
[5]Michael Bottcher and Ulrich Knauer,Endomorphism spectra of graphs,Discrete Mathematics,109,(1992),45-57.
[6]S.Fan,On End-regular graphs,Discrete Mathematics,159,(1996),95-102.
[7]S.Fan,Green's relation on endomorphism monoids of graphs,Journal of Jinan University,16,(1995),39-44.
[8]S.Fan,Retractions of split graphs and End-orthodox split graphs,Discrete Methematies,257,(2002),161-164.
[9]W.Li and J.chen,Endomorphism-regularity of split graphs,Euro.J.Combinatorics,22,(2001),207-216.
[10]W.Li,Graphs with regular monoid,Discrete Mathematics,265,(2003),105-118.
[11]W.Li,A regular endomorphism of a graph and its inverse,Mathematika,41,(1994),189-198.
[12]Ulrich Knauer and Martin Nieporte,Endomorphism of graphs Ⅰ.The monoids of strong endomorphisms,Arch.Math,52,(1989),607-614.
[13]Ulrich Knauer,Endomorphisms of graphs Ⅱ.Various unretractive graphs,Arch.Math,55,(1990),193-203.
[14]W.Li,Various inverses of a strong endomorphism of a graph,Discrete Mathematics,300,(2005),245-255.
[15]H.Hou,Y.Luo and Z.Chen,The endomorphism monoid of P_n,European Journal of Combinatorics (to appear).
[16]W.Li,Green's relations on the strong endomorphism monoid of a graph,Semigroup Forum,47,(1993),209-214.
[17] H.Hou,Y.Luo and X.Fan, End-regular(-orthodox) graphs which is the join of split graphs,(to appear).
[18] S.Fan, Graphs whose strong endomorphism of a graph, Arch.Math, 73,(1999), 419-421.
[19] William R.Nico, On the regularity of semidirect products, Journal of algebra, 80,(1986), 29-36.
[20] U.Knauer, Unretractive and S-unretractive joins and lexicographic products of graphs, J.Graph Theory, 3,(1987), 429-440.
[21] L.Marki, Problems raised at the problem session of the Colloquium on semigroups in Szeged, August 1987, Semigroup Forum 37,(1988), 367-373.
[22] P.Petrich and Norman R.Reilly, Completely regular semigroups, John Wiley & Sons, Inc., New York, 1999.
[23] E.Wilkeit, Graphs with Regular endomorphism monoid, Arch.Math, 66,(1996), 344-352.
[24] U.Nummert, On the monoid of the strong endomorphisms of wreath products of graphs, Matem.Zam, 41, (1987), 844-853.
[25] E.Wilkeit, The retracts of Hamming graphs, Discrete Math, 102, (1992), 197-218.
[26] V.Fleischer, On the wreath product of monoids with catefories, Proc.Acak.Sci.Estonian, SSR, 35, (1986), 27-34.
[27] Y.Luo, Y.Qin and H.Hou, Split graphs whose half-strong(localy strong) endomorphism forms a monoid,(to appear).
[28] H.Hou, X.Fan and Y.Luo, The endomorphism type of generalized polygon, Southeast Asian Bulletin of Mathematics (to appear).
[29] H.Hou and Y.Luo, The half-strong endomorphism of the join of two split graphs(to appear).
[2]F.Harary,Graph Theory,Addison-Wesley Reading,(1969).
[3]J.M.Howie,Fundamentals of Semigroup Theory,Clarandon Press,(1995).
[4]Thomas W.Hungerford,Algebra,Springer Verlag,London,(1974).
[5]Michael Bottcher and Ulrich Knauer,Endomorphism spectra of graphs,Discrete Mathematics,109,(1992),45-57.
[6]S.Fan,On End-regular graphs,Discrete Mathematics,159,(1996),95-102.
[7]S.Fan,Green's relation on endomorphism monoids of graphs,Journal of Jinan University,16,(1995),39-44.
[8]S.Fan,Retractions of split graphs and End-orthodox split graphs,Discrete Methematies,257,(2002),161-164.
[9]W.Li and J.chen,Endomorphism-regularity of split graphs,Euro.J.Combinatorics,22,(2001),207-216.
[10]W.Li,Graphs with regular monoid,Discrete Mathematics,265,(2003),105-118.
[11]W.Li,A regular endomorphism of a graph and its inverse,Mathematika,41,(1994),189-198.
[12]Ulrich Knauer and Martin Nieporte,Endomorphism of graphs Ⅰ.The monoids of strong endomorphisms,Arch.Math,52,(1989),607-614.
[13]Ulrich Knauer,Endomorphisms of graphs Ⅱ.Various unretractive graphs,Arch.Math,55,(1990),193-203.
[14]W.Li,Various inverses of a strong endomorphism of a graph,Discrete Mathematics,300,(2005),245-255.
[15]H.Hou,Y.Luo and Z.Chen,The endomorphism monoid of P_n,European Journal of Combinatorics (to appear).
[16]W.Li,Green's relations on the strong endomorphism monoid of a graph,Semigroup Forum,47,(1993),209-214.
[17] H.Hou,Y.Luo and X.Fan, End-regular(-orthodox) graphs which is the join of split graphs,(to appear).
[18] S.Fan, Graphs whose strong endomorphism of a graph, Arch.Math, 73,(1999), 419-421.
[19] William R.Nico, On the regularity of semidirect products, Journal of algebra, 80,(1986), 29-36.
[20] U.Knauer, Unretractive and S-unretractive joins and lexicographic products of graphs, J.Graph Theory, 3,(1987), 429-440.
[21] L.Marki, Problems raised at the problem session of the Colloquium on semigroups in Szeged, August 1987, Semigroup Forum 37,(1988), 367-373.
[22] P.Petrich and Norman R.Reilly, Completely regular semigroups, John Wiley & Sons, Inc., New York, 1999.
[23] E.Wilkeit, Graphs with Regular endomorphism monoid, Arch.Math, 66,(1996), 344-352.
[24] U.Nummert, On the monoid of the strong endomorphisms of wreath products of graphs, Matem.Zam, 41, (1987), 844-853.
[25] E.Wilkeit, The retracts of Hamming graphs, Discrete Math, 102, (1992), 197-218.
[26] V.Fleischer, On the wreath product of monoids with catefories, Proc.Acak.Sci.Estonian, SSR, 35, (1986), 27-34.
[27] Y.Luo, Y.Qin and H.Hou, Split graphs whose half-strong(localy strong) endomorphism forms a monoid,(to appear).
[28] H.Hou, X.Fan and Y.Luo, The endomorphism type of generalized polygon, Southeast Asian Bulletin of Mathematics (to appear).
[29] H.Hou and Y.Luo, The half-strong endomorphism of the join of two split graphs(to appear).