A connected bipartite graph is called Hamilton-laceable, a term apparently introduced in Simmons (1978),
if it has a 
Hamiltonian path for all pairs of vertices 
and 
,
where 
belongs to one set of the bipartition, and 
to the other.
A bipartite graph whose detour matrix elements 
are maximal for all 
and 
corresponding to different elements of the vertex bipartition
is therefore Hamilton-laceable.
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 one vertex in one set of the bipartition to a vertex in the other set must contain an odd number of edges (i.e., edge endpoints alternate
between bipartition components), the number of vertices 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
since one can always find two vertices 
and 
from different components that contain an edge 
, the definition of Hamilton-laceable requires that a Hamiltonian
path exists starting at 
and ending at 
, and 
connects the ends of this path 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 separate components of the
bipartition). 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). 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 is hamilton-laceable iff it has at least
one even index (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 and therefore Hamilton-laceable.
Shi and Niu (2009) conjectured that every complete transposition graph has a Hamilton decomposition when its degree is even and a quasi-Hamilton decomposition when its 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.
A collection of common graphs can be checked precomputed values in the Wolfram Language using GraphData[g, "HamiltonLaceable"].
-Dimensional Rectangular Lattices Are Hamilton-Laceable."
In