Hamilton-Laceable Graph

A Hamilton-laceable graph is a connected bipartite graph with a Hamiltonian path for every pair of vertices and in different bipartition classes. The term was apparently introduced by Simmons (1978).

A bipartite graph whose detour matrix elements equal , where is its vertex count, for all and corresponding to vertices in different bipartition classes is therefore Hamilton-laceable.

A strongly Hamiltonian-laceable graph additionally has a path of length between every pair of distinct vertices in the same bipartition class, where is the vertex count (Hsieh et al. 2000).

Including the singleton graph (which is generally considered both traceable and bipartite), the numbers of Hamilton-laceable graphs on , 2, ... vertices are 1, 1, 0, 1, 0, 2, 0, 12, 0, 226, 0, ... (OEIS A236219), the first few of which are illustrated above.

Since a Hamiltonian path from a vertex in one bipartition class to a vertex in the other class must contain an odd number of edges (i.e., edge endpoints alternate between bipartition classes), the vertex count in a Hamilton-laceable graph must be even (with the exception of the degenerate case ). With the exception of , Hamilton-laceable graphs are also Hamiltonian. For vertex count at least 4, choose an edge joining the two bipartition classes. The definition supplies a Hamiltonian path starting at and ending at , and connects its ends into a Hamiltonian cycle.

Not all even-vertex count, bipartite, Hamiltonian graphs are Hamilton-laceable. For example, the domino graph has 6 vertices and is Hamiltonian and bipartite but contains no Hamiltonian path connecting the vertices of the middle rung (which lie in different bipartition classes). The numbers of such graphs on , 4, ... nodes are 0, 0, 2, 12, 253, ....

Dupuis and Wagon (2015) conjectured that all bipartite Hamiltonian vertex-transitive graphs are Hamilton-laceable except for even cycle graphs with (Dupuis and Wagon 2015; Gregor et al. 2024, p. 35:2). A slightly more general and precise statement of this conjecture can be made in terms of H^*-connected graphs.

Assuming , the grid graph is Hamilton-laceable iff or at least one of is even and . A grid graph in three or more dimensions, with every side length at least 2, is Hamilton-laceable iff at least one side length is even (Simmons 1978).

All hypercube graphs are Hamilton-laceable, a result that follows from results of Chen and Quimpo (1981).

Baggett and Yan (2026) proved that the complete transposition graph is paired 2-disjoint-path-coverable for and therefore Hamilton-laceable. The cases and are Hamilton-laceable directly.

Shi and Niu (2009) conjectured that every complete transposition graph has a Hamilton decomposition when its vertex degree is even and a quasi-Hamilton decomposition when its vertex degree is odd. This conjecture remains open; Hamilton-laceability does not provide the required edge decomposition.

The knight graph is Hamilton-laceable iff , , and at least one of , is even (Dupuis and Wagon 2015).

Pensaert (2002) conjectured that for with , the generalized Petersen graph is Hamilton-laceable if is even and is odd, and Hamilton-connected otherwise.

Precomputed values for common graphs can be obtained in the Wolfram Language using GraphData[g, "HamiltonLaceable"].