图的字典序积和自同态幺半群

The Endomorphism Monoids of the Lexicographic Product of Two Graphs

Ｆ．Ｈａｒａｒｙ￣［１］和Ｇ．Ｓａｂｉｄｕｓｓｉ￣［２］考虑过图Ｘ和ｙ的字典序积Ｘ［Ｙ］的自同构群ＡｕｔＸ［Ｙ］与它们各自的自同构群的圈积ＡｕｔＸ［ＡｕｔＹ］的关系，并给出了两者相等的一种刻划．在本文，我们考虑更广意义上的问题，即Ｘ［Ｙ］的自同态幺半群ＥｎｄＸ［Ｙ］与各自的自同态幺半群的圈积ＥｎｄＸ［ＥｎｄＹ］的关系，也给出了两者相等的一种刻划，同时得到了下面结果：如果Ｘ和Ｙ都是不含Ｋ＿３导出子图的连通图，且其中之一图有奇数围长，那么ＥｎｄＸ［Ｙ］＝ＥｎｄＸ［ＥｎｄＹ］．

The criterions for the automorphism group of the lexicographic products of two and G. Sabidussi￣[2].In this paper, the corresponding criterion for endomorphism monlid is given. In the meantime, the following result is obtained:If X and Y are K￣3 free connectedgraphs, and either of two graphs has odd girth,then the endomorphism monoid End X[Y] of the lexicographic product X[Y]of X and Y coincides with the wreath product End X[ End Y]Of their monoid End Xand End Y.