graph-theory - n = 1 mod 4, (n-1)/2-regular 的图中的哈密顿循环？

Question

考虑一个 n 阶图，其中 n 是 1 mod 4（即五边形、九边形等），并假设它是 (n-1)/2-正则图。此外（可能可选）假设它和它的补码都是连接的。

这种类型的图是否可以被验证为哈密顿量，如果可以，证明将如何进行？

Answer 1

根据 Ore 定理

A graph with n vertices (n ≥ 3) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n or greater

在您的情况下，它是(n-1)/2常规图。因此，非相邻顶点的总和将为(n-1)。

此外，您可以使用 Tutte(1956) 的以下定理：

A 4-connected planar graph has a Hamiltonian cycle.

根据我的观点，如果给定图的所有顶点上都有一个 4 连通平面图是子图，那么就会存在哈密顿循环。