We investigate Cayley graphs of finite semigroups and monoids. First, we look at semigroup digraphs, i.e., directed Cayley graphs of semigroups, and give a Sabidussi-type characterization in the case of monoids. We then correct a proof of Zelinka from '81 that characterizes semigroup digraphs with outdegree $1$. Further, answering a question of Knauer and Knauer, we construct for every $k\geq 2$ connected $k$-outregular non-semigroup digraphs. On the other hand, we show that every sink-free directed graph is a union of connected components of a monoid digraph. Second, we consider monoid graphs, i.e., underlying simple undirected graphs of Cayley graphs of monoids. We show that forests and threshold graphs form part of this family. Conversely, we construct the -- to our knowledge -- first graphs, that are not monoid graphs. We present non-monoid graphs that are planar, have arboricity $2$, and treewidth $3$ on the one hand, and non-monoid graphs of arbitrarily high connectivity on the other hand. Third, we study generated monoid trees, i.e., trees that are monoid graphs with respect to a generating set. We give necessary and sufficient conditions for a tree to be in this family, allowing us to find large classes of trees inside and outside the family.
翻译:我们调查了Cayley的定数半组和单项图。 首先,我们查看了半组图,即指示的Cayley 半组图,在单项图中给出了Sabidussi型的特征特征。 然后我们纠正了81年的Zelinka的证明,该证明是半组的半组图,其特征为1美元以上。 此外,在回答Knauer和Knauer的问题时,我们为每2美元建造一个连接于$@k\geq 2 的连接点,它连接于美元外的普通非半组图。 另一方面,我们显示每个无水层的定向图都是单项图中连接的成分。 其次,我们考虑的是单项图,即作为单项图的简单非定向图。 我们展示了森林和门槛图是这个家族的一部分。 相反,我们建造的 -- 第一个数据是非单项图,它不是单项图。 我们展示了非单项图的图表是非单项图, 我们的图中的条件是单项单项图中的一部分。