Hamilton-Laceable 图

一个连通二部图被称为 Hamilton-laceable 图，这个术语显然由 Simmons (1978) 引入，如果对于所有顶点对 和 ，其中 属于二划分的一个集合，而 属于另一个集合，它都存在 哈密顿路径。

一个二部图，如果其迂回矩阵元素 对于所有 和 （对应于顶点二划分的不同元素）都是最大的，那么它就是 Hamilton-laceable 图。

包括孤立点图（通常认为它既是可追踪的又是二部的），顶点数为 , 2, ... 的 Hamilton-laceable 图的数量是 1, 1, 0, 1, 0, 2, 0, 12, 0, 226, 0, ... （OEIS A236219），其中前几个示例如上所示。

由于从二划分的一个集合中的一个顶点到另一个集合中的一个顶点的哈密顿路径必须包含奇数条边（即，边的端点在二划分的各部分之间交替），因此 Hamilton-laceable 图的顶点数必须是偶数（除了退化情况 ）。 除了 之外，Hamilton-laceable 图也是哈密顿图，因为总能找到来自不同部分的两个顶点 和 ，它们之间包含一条边 ，Hamilton-laceable 的定义要求存在一条哈密顿路径，从 开始到 结束，并且 将这条路径的端点连接成一个哈密顿环。

并非所有偶数顶点数、二部、哈密顿图都是 Hamilton-laceable 图。例如，多米诺骨牌图 有 6 个顶点，是哈密顿图和二部图，但不包含连接中间梯级的顶点的哈密顿路径（这些顶点位于二划分的不同部分）。顶点数为 , 4, ... 的这种图的数量是 0, 0, 2, 12, 253, ....

Dupuis 和 Wagon (2014) 推测，除了 且 的偶圈图之外，所有二部哈密顿顶点传递图都是 Hamilton-laceable 图。可以用 H-*-连通图来对这个猜想做一个稍微更通用和精确的陈述。

假设 ，网格图 是 Hamilton-laceable 图，当且仅当 或者 中至少有一个是偶数且 。网格图在三个或更多维度中是 Hamilton-laceable 图，当且仅当它至少有一个偶数索引 (Simmons 1978)。

所有超立方体图都是 Hamilton-laceable 图，这个结果来源于 Chen 和 Quimpo (1981) 的研究结果。

马步图是 Hamilton-laceable 图，当且仅当 , , 且 , 中至少有一个是偶数 (Dupuis 和 Wagon 2014)。

Pensaert (2002) 推测，对于 且 ，如果 是偶数且 是奇数，则广义 Petersen 图 是 Hamilton-laceable 图，否则是 Hamilton-连通图。

可以使用 Wolfram 语言中的预计算值来检查一些常见图的集合。GraphData[g, "HamiltonLaceable"].