Hamilton-Laceable Graph

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 (2014) conjectured that all bipartite Hamiltonian vertex-transitive graphs are Hamilton-laceable except for even cycle graphs  with . 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).

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

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"].

REFERENCES

Chen, C. C. and Quimpo, N. F. "On Strongly Hamiltonian Abelian Group Graphs." In Combinatorial Mathematics. VIII. Proceedings of the Eighth Australian Conference held at Deakin University, Geelong, August 25-29, 1980 (Ed. K. L. McAvaney). Berlin: Springer-Verlag, pp. 23-34, 1981.

Dupuis, M. and Wagon, S. "Laceable Knights." To appear in Ars Math Contemp.Pensaert, W. P. J. "Hamilton Paths in Generalized Petersen Graphs." Thesis. Waterloo, Ontario, Canada. January 2002. http://etd.uwaterloo.ca/etd/wpjpensaert2002.pdf.

Simmons, G. J. "Almost All -Dimensional Rectangular Lattices Are Hamilton-Laceable." In Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (Ed. F. Hoffman, D. McCarthy, R. C. Mullin, and R. G. Stanton). Winnipeg, Manitoba: Utilitas Mathematica Publishing, pp. 649-661, 1978.

Sloane, N. J. A. Sequence A236219 in "The On-Line Encyclopedia of Integer Sequences."