自补图

自补图是与它的补图同构的图。简单自补图在 , 2, ... 个节点上的数量分别为 1, 0, 0, 1, 2, 0, 0, 10, ... (OEIS A000171)。前几个分别对应于一个节点的平凡图，路径图 和圈图 。

每个自补图不仅是连通的，而且是可迹的 (Clapham 1974; Camion 1975; Farrugia 1999, p. 52)。此外，所有自补图的图直径为 2 或 3 (Sachs 1962; Skiena 1990, p. 187)。对于具有 个顶点的自补图，对于每个整数 ，都存在长度为 的图圈 (Rao 1977; Farrugia 1999, p. 51)。因此，具有 个顶点的自补图的图周长为 (即，该图是哈密顿图), , 或 (Furrigia 1999, p. 51)。

根据定义，自补图必须恰好具有可能边总数的一半，即，对于具有 个顶点的自补图，有 条边。由于 必须能被 4 整除，因此 或 1 (mod 4)。

存在多项式时间条件来确定自补图是否是哈密顿图。

n 个节点上的自补图的数量可以从“图多项式” 中获得，该多项式源自用于枚举简单图数量的 Pólya 枚举定理，为 。