关于刚性正则图与 Babai–Pultr 问题
On rigid regular graphs and a problem of Babai and Pultr
Kolja Knauer, Gil Puig i Surroca
AI 速读 基于摘要
作者报告构造了任意奇数围长 g≥7 的无穷多个互不同构的刚性 d-正则图,确定了 d≥3 时刚性 d-正则图的最小阶,并用该构造证明每个有限幺半群都同构于某个正则图的自同态幺半群。
math.CO · cs.DM
查看原文摘要
A graph is rigid if it only admits the identity endomorphism. We show that for every $d\ge 3$ there exist infinitely many mutually rigid $d$-regular graphs of arbitrary odd girth $g\geq 7$. Moreover, we determine the minimum order of a rigid $d$-regular graph for every $d\ge 3$. This provides strong positive answers to a question of van der Zypen [https://mathoverflow.net/q/296483, https://mathoverflow.net/q/321108]. Further, we use our construction to show that every finite monoid is isomorphic to the endomorphism monoid of a regular graph. This solves a problem of Babai and Pultr [J. Comb. Theory, Ser. B, 1980].