On the minimum order of graphs with given semigroup |
| |
Authors: | Václav Koubek Vojtěch Rödl |
| |
Affiliation: | 1. Faculty of Mathematics and Physics, Malostranske nam. 25, 11800 Prague 1, Czechoslovakia;2. Faculty of Physical Engineering, Department of Mathematics, Husova 5, 11000 Praha 1, Czechoslovakia |
| |
Abstract: | Denote by M(n) the smallest positive integer such that for every n-element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that . Moreover, for almost all n-element monoids M there is a graph G with at most 12 · n · log2n + n vertices such that End(G) is isomorphic to M. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|