radoszewski2011hamiltonian (667B)
1 # Radoszewski2011hamiltonian 2 3 Studies when the [graph_square] of an [undirected_graph] has [Hamiltonian_cycle] and [Hamiltonian_path] 4 5 [harary1971trees] shows that [graph_square] of [tree] contains a [Hamiltonian_cycle] iff it is a [caterpillar_tree] 6 7 They show that [graph_square] of [tree] contains a [Hamiltonian_path] iff it is a [horsetail_graph]. Testing this, and finding the path, can be done in [linear_time], and [linear_time] [preprocessing] is sufficient to test in constant time, given (u, v), whether there is a [Hamiltonian_path] from u to v. 8 9 Up: [academic_paper] on [hamiltonian_cycle] 10 11 See also: [hamiltonian_cycle_square], [hamiltonian_cycle_cube]