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

Every self-complementary graph is traceable (Clapham 1974; Camion 1975; Farrugia 1999, p. 52).

The following table lists some named graphs that are traceable but not Hamiltonian.

graph
theta-0 graph	7
Petersen graph	10
Herschel graph	11
Blanuša snarks	18
flower snark	20
Coxeter graph	28
double star snark	30
Tutte's graph	46
Szekeres snark	50
McLaughlin graph	276

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.

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.