固定数

设 为一个有限图， 为 的一个顶点。 的稳定子, , 是群元素 的集合，其中 是 图自同构 群。顶点集 的顶点稳定子定义为 。如果 , 则顶点 被群元素 固定。

如果 是平凡的，则顶点集 称为图 的固定集。图 的固定集的最小基数称为其固定数 (Erwin and Harary 2006, Gibbons and Laison 2009)。

固定数是整数，其范围从 0 (对于 恒等图) 到 (对于 完全图 或 空图)，其中 是图的 顶点数。

一个图的固定数等于其 补图 的固定数。

Greenfield (2011) 总结了若干图族的固定数值，并讨论了若干固定数算法。

Gibbons 和 Laison (2009) 提出了一个 贪婪算法 来确定固定数，并指出该算法的定义尚不明确。随后，Greenfield (2011) 发现了 12 顶点的 Greenfield 图，表明该算法的结果可能取决于每一步选择的顶点，因此确定了该算法仅提供图的固定数的上限。Greenfield 图（Greenfield 假设它是最小的可能的例外图）以及其他一些此类例外图（E. Weisstein，2023 年 6 月 6 日）在上面进行了说明，并在下表中进行了总结。

顶点数	固定数	贪婪固定数	图
12	3	4	Greenfield 图
16	2	3	16-立方图 20
16	2	3	-正则非平面直径图
20	5	7	Folkman 图

然而，除了少数此类情况外，对于几乎所有小的命名或列表简单的图，贪婪算法确实给出了实际的固定数。