跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

A graph is rigid if it only admits the identity endomorphism. We show that for every d≥3d\ge 3 there exist infinitely many mutually rigid dd-regular graphs of arbitrary odd girth g≥7g\geq 7. Moreover, we determine the minimum order of a rigid dd-regular graph for every d≥3d\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].

作者备注:34 pages, 13 figures, journal (revised) version

期刊信息:European Journal of Combinatorics 140 (2027) 104466

AI 论文解读

基于摘要 · 非全文审阅

作者报告构造了任意奇数围长 g≥7 的无穷多个互不同构的刚性 d-正则图,确定了 d≥3 时刚性 d-正则图的最小阶,并用该构造证明每个有限幺半群都同构于某个正则图的自同态幺半群。

正在读取账号与研究记录…

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 d≥3d\ge 3 there exist infinitely many mutually rigid dd-regular graphs of arbitrary odd girth g≥7g\geq 7. Moreover, we determine the minimum order of a rigid dd-regular graph for every d≥3d\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].

查看此版本解读 →查看此版本原文 ↗