|
|||||
|
|
On the number of graphs with a given endomorphism monoid |
|
| Authors: | Vá clav Koubek,Vojtěch Rö dl |
| Affiliation: | a Department of Theoretical Computer Science and Mathematical Logic, The Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00 Praha 1, Czech Republic b Department of Mathematics, Emory University, Atlanta, USA |
| Abstract: | 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  . |
| Keywords: | Endomorphism monoid of graph Rigid graph |
| 本文献已被 ScienceDirect 等数据库收录！ | |