A traceable graph is a graph that possesses a Hamiltonian path. Hamiltonian graphs are therefore traceable,
but the converse is not necessarily true. Graphs that are not traceable are said
to be untraceable.
The numbers of traceable graphs on , 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864),
where the singleton graph is conventionally considered traceable. The first few are
illustrated above, with a Hamiltonian path indicated
in orange for each.
-dimensional grid
graphs of arbitrary shape and dimension appear to be traceable, though a proof
of this assertion in its entirely does not seem to appear in the literature (cf.
Simmons 1978, Hedetniemi et al. 1980, Itai et al. 1982, Zamfirescu
and Zamfirescu 1992).
The following table lists some named graphs that are traceable but not Hamiltonian.
Camion, P. "Hamiltonian Chains in Self-Complementary Graphs." In Colloque sur la théorie des graphes (Paris, 1974)
(Ed. P. P. Gillis and S. Huyberechts). Cahiers du Centre Études
de Recherche Opér. (Bruxelles)17, pp. 173-183, 1975.Clapham,
C. R. J. "Hamiltonian Arcs in Self-Complementary Graphs." Disc.
Math.8, 251-255, 1974.Farrugia, A. "Self-Complementary
Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999.
http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Godsil,
C. and Royle, G. "Hamilton Paths and Cycles." C§3.6 in Algebraic
Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.Gould,
R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th.15,
121-157, 1991.Hedetniemi, S. M.; Hedetniemi, S. T.; and Slater,
P. S. "Which Grids Are Hamiltonian?" Congr. Numer.29,
511-524, 1980.Itai, A.; Papadimitriou, C. H.; and Szwarcfiter,
J. L. "Hamilton Paths in Grid Graphs." SIAM J. Comput.11,
676-686, 1982.Mütze, T. "On Hamilton Cycles in Graphs Defined
by Intersecting Set Systems." Not. Amer. Soc.74, 583-592, 2024.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 A057864 in "The On-Line Encyclopedia
of Integer Sequences."Thomassen, C. "Hypohamiltonian and Hypotraceable
Graphs." Disc. Math.9, 91-96, 1974.Zamfirescu, C.
and Zamfirescu, T. "Hamiltonian Properties of Grid Graphs." SIAM J.
Disc. Math.5, 564-570, 1992.