头条新闻

格雷图是同类图中最小的图

作者：Eric W. Weisstein

2002年4月9日——在一篇提交给《离散数学》的论文中，一个数学家团队解决了确定最小的三次图的问题，该三次图是半对称的（即，边传递但不是顶点传递的）。三次图简单来说是顶点和边的集合（即，在图论意义上的图），其中每个顶点发出三条边，不允许连接顶点到自身的环和两个节点之间的多条边（即，该图是所谓的简单图）。边传递图是指在所谓的自同构群的某个元素下，任意两条边都是等价的图，顶点传递图的定义类似。图的自同构群是从图到自身并保留图结构的函数的群（在群论意义上）。

Marion C. Gray 于 1932 年发现了一个具有 54 个顶点的半对称三次图，并由 Bouwer (1968) 首次发表。该图（如上图所示）被命名为 格雷图，以纪念其最初的发现者。自发表以来，格雷图一直是已知的最小的三次半对称传递图的例子。在即将发表的一篇论文中，Malnic 等人最终证明格雷图实际上是最小的此类可能的图。