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 Graph

Explore with Wolfram|Alpha


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., 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 Graph

Cite this as:

Weisstein, Eric W. "Traceable Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications