### Traceability of locally hamiltonian and locally traceable graphs

*Johan de Wet, Susan van Aardt*

#### Abstract

If P is a given graph property, we say that a graph G is locally P if has property P for every v ∈ V (G) where is the induced graph on the open neighbourhood of the vertex v. Pareek and Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions.
Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph?
Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph?
We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.

Full Text: PDF