On the number of graphs with a given endomorphism monoid |
| |
| Authors: | Václav Koubek Vojtěch Rödl |
| |
| Institution: | 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 等数据库收录！ |
|
