Traceable Graph
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 👁 n=1
, 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864),
where the singleton graph 👁 K_1
is conventionally considered traceable. The first few are
illustrated above, with a Hamiltonian path indicated
in orange for each.
Every self-complementary graph is traceable (Clapham 1974; Camion 1975; Farrugia 1999, p. 52).
The Lovász conjecture states that without exception, every connected vertex-transitive graph is traceable.
👁 d
-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.
See also
Eulerian Cycle, Hamilton-Connected Graph, Hamiltonian Graph, Hypotraceable Graph, Königsberg Bridge Problem, Lovász Conjecture, Unicursal Circuit, Untraceable GraphExplore with Wolfram|Alpha
More things to try:
References
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 👁 n
-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.
Referenced on Wolfram|Alpha
Traceable GraphCite this as:
Weisstein, Eric W. "Traceable Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TraceableGraph.html