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 的连接点,它连接于美元外的普通非半组图。 另一方面,我们显示每个无水层的定向图都是单项图中连接的成分。 其次,我们考虑的是单项图,即作为单项图的简单非定向图。 我们展示了森林和门槛图是这个家族的一部分。 相反,我们建造的 -- 第一个数据是非单项图,它不是单项图。 我们展示了非单项图的图表是非单项图, 我们的图中的条件是单项单项图中的一部分。

0
下载
关闭预览

相关内容

【杜克-Bhuwan Dhingra】语言模型即知识图谱,46页ppt
专知会员服务
65+阅读 · 2021年11月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
159+阅读 · 2020年1月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【荟萃】知识图谱论文与笔记
专知
71+阅读 · 2019年3月25日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】RNN无损压缩方法DeepZip(附代码)
机器学习研究会
5+阅读 · 2018年1月1日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年11月25日
Arxiv
0+阅读 · 2021年11月25日
Arxiv
7+阅读 · 2021年7月5日
Arxiv
101+阅读 · 2020年3月4日
Arxiv
53+阅读 · 2018年12月11日
VIP会员
相关VIP内容
【杜克-Bhuwan Dhingra】语言模型即知识图谱,46页ppt
专知会员服务
65+阅读 · 2021年11月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
159+阅读 · 2020年1月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
【荟萃】知识图谱论文与笔记
专知
71+阅读 · 2019年3月25日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】RNN无损压缩方法DeepZip(附代码)
机器学习研究会
5+阅读 · 2018年1月1日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Arxiv
0+阅读 · 2021年11月25日
Arxiv
0+阅读 · 2021年11月25日
Arxiv
7+阅读 · 2021年7月5日
Arxiv
101+阅读 · 2020年3月4日
Arxiv
53+阅读 · 2018年12月11日
Top
微信扫码咨询专知VIP会员