Hamilton-Laceable Graph
المؤلف:
Sloane, N. J. A
المصدر:
Sequence A236219 in "The On-Line Encyclopedia of Integer Sequences."
الجزء والصفحة:
...
11-5-2022
2102
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 ![(m,n) in <span style=]()
{(1,1),(1,2),(2,2)}" src="https://mathworld.wolfram.com/images/equations/Hamilton-LaceableGraph/Inline24.svg" style="height:22px; width:232px" /> 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."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
