Traceable Graph
المؤلف:
Clapham, C. R. J.
المصدر:
. "Hamiltonian Arcs in Self-Complementary Graphs." Disc. Math. 8
الجزء والصفحة:
...
13-5-2022
1666
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
