← 研踪 PaperTrailarXiv:2502.11421 · v2
On rigid regular graphs and a problem of Babai and Pultr
关于刚性正则图与 Babai–Pultr 问题
首次提交 2025-02-17 12:21
版本更新 2026-11-05 23:25
雷达观测 2026-11-06 13:11
摘要
A graph is rigid if it only admits the identity endomorphism. We show that for every there exist infinitely many mutually rigid -regular graphs of arbitrary odd girth . Moreover, we determine the minimum order of a rigid -regular graph for every . 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].
作者备注:34 pages, 13 figures, journal (revised) version
期刊信息:European Journal of Combinatorics 140 (2027) 104466
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-05 23:25 · 最新观测版本
On rigid regular graphs and a problem of Babai and Pultr
A graph is rigid if it only admits the identity endomorphism. We show that for every there exist infinitely many mutually rigid -regular graphs of arbitrary odd girth . Moreover, we determine the minimum order of a rigid -regular graph for every . 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].
查看此版本解读 →查看此版本原文 ↗